连续子数组的最大和

题目

牛客网

例如:{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;
}