典型的动态规划问题

状态定义：dp[i]表示以i结尾的连续子数组的最大和。
状态转移方程：dp[i] = max(array[i], dp[i-1]+array[i])

代码一：

以下代码用变量dpMax 存储dp[i]：

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        int dpMax = array[0];
        for (int i = 1; i < array.length; i++) {
            dpMax = Math.max(array[i], array[i] + dpMax);
            max = Math.max(max, dpMax);
        }
        return max;
    }
}

代码二：

dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。使用一个变量max记录最大的dp值返回即可。
以下代码直接用变量array数组存储连续和：

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            array[i]+= Math.max(array[i - 1], 0);
            max = Math.max(max, array[i]);
        }
        return max;
    }
}