连续子数组的最大和

给一个数组，返回它的最大连续子序列的和。例如 [6,-3,-2,7,-15,1,2,2] 连续子序列的最大和为 8（从第 0 个开始，到第 3 个为止)。注意：连续子序列的起始下标不一定是 0。

解题思路

采用动态规划的思想，假设 dp[n] 表示以当前元素为截止点的连续子序列的最大和，那么可以得出状态转移方程 dp[n] = dp[n - 1] + array[n]

题目只要求最大值，因此每次都可以使用一个变量 max 记录最大和，变量 res 记录当前子序列的最大和，再将 max 与 res 比较，将更大的值赋给 max，最后返回 max 即可

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int res = array[0];
        int max = array[0];
        for(int i = 1; i < array.length; i++) {
        	// 当前子序列的最大和，要么是前一个子序列加上当前值，要么只是当前值
            res = Math.max(res + array[i], array[i]);
            max = Math.max(res, max);
        }
        return max;
    }
}