描述
输入一个长度为n的整型数组a，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
示例1
输入：[1,-2,3,10,-4,7,2,-5]
返回值：18
说明：输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10,-4,7,2}，因此输出为该子数组的和 18。
思路:
采用的是动态规划的思路。

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp =new int[array.length];
        int maxSum=array[0];
        dp[0]=array[0];
        for(int i=1;i<array.length;i++){
            int sum=dp[i-1]+array[i];
            if(sum<array[i]){
                dp[i]=array[i];
            }else{
                dp[i]=sum;
            }
            if(dp[i]>maxSum){
                maxSum=dp[i];
            }
        }
        return maxSum;
    }
}

忘记了看Leetcode的图文讲解:

https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/