42 连续子数组的最大和

牛客

描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

示例1
输入：[1,-2,3,10,-4,7,2,-5]
返回值：18

说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2
输入：[2]
返回值：2

示例3
输入：[-10]
返回值：-10

---

动态规划。以当前值为子数组结尾的最大子数组和为当前的值或当前值加上以上一个数为结尾的最大子数组和。 f(n) = max( n , f(n-1)+n )

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max=array[0];
        int pre=0, cur;
        for(int i:array){
            cur=pre+i>i?pre+i:i;
            pre=cur;
            if(cur>max) max=cur;
        }
        return max;
    }
}