FindGreatestSumOfSubArray.md

连续子数组的最大和

题目

牛客网

例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

解题思路

通过动态规划计算最大和，$$f(i)$$ 定义为以第 $$i$$ 个数字结尾的子数组的最大和，那么 $$max(f(i))$$ 就有以下公式：

$$ max(f(i))=\begin{cases} num[i] & i=0 or f(i)<0\\ num[i]+f(i) & i\ne0 and f(i)>0 \end{cases} $$

public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null || array.length == 0) {
        return 0;
    }

    int max = array[0];
    int sum = 0;
    for (int a : array) {
        if (sum + a > a) {
            sum += a;
        } else {
            sum = a;
        }

        if (sum > max) {
            max = sum;
        }
    }

    return max;
}