题解 | #连续子数组的最大和#

最大子数组的和一定是当前元素和之前最大连续子数组的和叠加在一起形成的，
要么是只是当前元素的值，要么是之前连续子数组的和加上当前元素的值。
可以用动态规划

public class Solution {
    //最大子数组的和一定是由当前元素和之前最大连续子数组的和叠加在一起形成的，
    //因此需要遍历n个元素，看看当前元素和其之前的最大连续子数组的和能够创造新的最大值。
    public int FindGreatestSumOfSubArray(int[] array) {
        int len=array.length;
        int[]dp=new int[len];
        dp[0]=array[0];
        int max=dp[0];
        for(int i=1;i<len;i++){
            dp[i]= Math.max(dp[i-1]+array[i],array[i]);
            max=Math.max(dp[i],max);
        }
        return max;
    }
}