连续子数组的最大和（动态规划）

发表于 | 分类于

题目

输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

示例

输入：{1，-2，3，10，-4，7，2，-5}
输出：18

题解

我们采用动态规划的思想，上一篇中我们介绍过动态规划要有状态和状态转化方程。状态：F(i)，以array[i]为末尾元素的子数组的和的最大值；状态转移方程，F(i)=max（F（i-1）+array[i] ， array[i]）；res:所有子数组的和的最大值，res=max(res,F(i))。最终res就是我们所要求的值。
如数组[6, -3, -2, 7, -15, 1, 2, 2]
初始状态： F（0）=6，res=6；
i=1: F（1）=max（F（0）-3，-3）=max（6-3，3）=3, res=max（F（1），res）=max（3，6）=6;
i=2：F（2）=max（F（1）-2，-2）=max（3-2，-2）=1,res=max（F（2），res）=max（1，6）=6;
i=3：F（3）=max（F（2）+7，7）=max（1+7，7）=8, res=max（F（2），res）=max（8，6）=8;
i=4：F（4）=max（F（3）-15，-15）=max（8-15，-15）=-7,res=max（F（4），res）=max（-7，8）=8;以此类推,最终res的值为8。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0){
            return 0;
        }
        int res =array[0];
        int max=array[0];
        for(int i=0;i<array.length;i++){
            max = Math.max(max+array[i],array[i]);
            res = Math.max(res,max);
        }
        return res;
    }
}