Kadane算法->动态规划

最大连续子数组和：函数名称是MaxSubArray(L); 初始条件是线性表L已存在且非空，请找出一个具有最大和的连续子数组（子数组最少包含一个元素），操作结果是其最大和；

1
2
3
4
5
6
7
8
9
10
11
int maxSubArray(int* nums, int numsSize) {
    int maxSum = nums[0];
    int curSum = nums[0];
    for (int i = 1; i < numsSize; i++) {
        curSum = curSum > 0 ? curSum + nums[i] : nums[i];
        if (curSum > maxSum) {
            maxSum = curSum;
        }
    }
    return maxSum;
}

链表类似