剑指offer.42-连续子数组的最大和

题目:输入一个整型数组,数组里有正数和负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为{1,-2,3,10,-4,7,2,-5},和最大的子数组为{3,10,-4,7,2},因此输出为该子数组的和18。

不管暴力枚举适不适合解题,我们都可以先分析一下它的时间复杂度。一个长度为n的数组,共有n(n+1)/2个子数组,所以要找出所有子数组中的最大的和值,需要O(n^2)的时间复杂度,不满足题目需求。往往最直观的解不是最优解

那我们看看动态规划是否可以呢?

这题很明显可以分解成子问题,设f(i)是以第i个数字结尾的子数组最大和,要想求得f(i)的最大和,我们肯定需要先求的f(i-1)的最大和...依次思路,现在的问题就变成了:当知道f(i-1)的最大和后,f(i)的最大和该是多少?

分析:假设有长度为n的数组data,如果f(i-1)的最大和是小于零的,那么加上f(i)后的值肯定是小于f(i-1),那此时f(i)的最大和应该等于data[i];如果f(i-1)的最大和是大于零的,那么加上f(i)后的值肯定是大于data[i]的,所以此时f(i)的最大和应该等于f(i-1)+data[i]

经过分析,我们可以得到下面的公式:

剑指offer.42-连续子数组的最大和

通过上面的公式,我们可以得到一系列的最大和,剩下的操作就是从这些和中找出最大的和即可。

代码如下:

public Integer findGreatestSumOfSubArray(int[] data) {
    if (data == null || data.length == 0) return null;

    int result = 0;
    int[] maxSum = new int[data.length]; // 辅助数组,记录以第i个数字结尾的子数组最大和
    for(int i = 0; i < data.length; i++) {
        if (i > 0 && maxSum[i-1] > 0) {
            maxSum[i] = maxSum[i-1] + data[i];
        } else {
            maxSum[i] = data[i];
        }
        result = result > maxSum[i] ? result : maxSum[i]; // 循环中顺带判断出最大值
    }

    return result;
}

只需要遍历一次data数组,所以时间复杂度为O(n),满足题目要求。

上一篇:c语言解决leetcode中最大子序和问题。


下一篇:luogu P7619 [COCI2011-2012#2] RASPORED