编程之美2.14 求数组的子数组之和的最大值

一个有N个整数元素的一维数组( A[0], A[1], ... , A[n-2], A[n-1])，子数组之和的最大值是什么?(要求子数组的元素是连续的)

 

例子：有数组( -2, 5, 3, -6, 4, -8, 6)，则其子数组之和的最大值为8，其对应的数组为(5,3)

 

《编程之美》最后给出了一个时间复杂度为O(n)的算法，实现的代码如下:

 

#include <stdio.h>

int maxSubSum(int* array, int length) {
	int nAll = array[length -1];
	int nStart = array[length-1];
	int i;
	for( i = length-2; i>=0; i--) {
		if(nStart < 0)
			nStart = 0;
		nStart += array[i];
		if(nStart > nAll) //若当前子数组之和大于nAll，则更新nAll
			nAll = nStart;
	}
	return nAll;
}

int main() {
	int a[7] = {-2,5,3,-6,4,-8,6};
	int maxSub = maxSubSum(a,7);
	printf("Max sub sum = %d\n",maxSub);
}

 

其中nAll保存当前的最大子数组之和，先定义初值为最后一个元素，

nStart保存当前的子数组之和，若为负数(最大和的子数组不可能包含当前子数组)，则在下次遍历时清零，重新寻找最大和的子数组

评论

9 楼 liguocai2009 2012-06-13  

我搞错了。。。
这条题目我刚开始想的是知道a[0]..a[i]子数组的最大值，推导出a[0]...a[i+1]子数组最大值，推导的关键是判断下面3者谁是最大值，最大值的那个就是a[0]...a[i+1]的子数组最大值
a[0]...a[i]的子数组最大值 + a[i+1]
a[i+1]
a[ a[0]...a[i]的最大值子数组的起始index ] 到 a[i+1]的和

这个算法是 O(n*n)。

看了看博文，发现博文是利用了数学，轻松地解决了问题...思路上的根本差别是，我是想由n推出n+1，而博文是利用数学规律
if c>=0
  a+c > a
else if c<0
  a+c <a

8 楼 liguocai2009 2012-06-13  

lagrangee 写道

david.org 写道

楼主正解，不过这题要是要求记录数组位置的话，估计就做不到 O(N) 的时间复杂度了

通过 if(nStart > nAll)  可以确定端点k，  获取nAll后从端点k顺序相加直到和等于nAll 还是O(n)

要位置的话仍然是O(n)啊。。。

7 楼 liguocai2009 2012-06-13  

这一题有一个非常重要的前提。。。最小值是0。。。否则怎么想都是o(n*n)

6 楼 lagrangee 2012-03-30  

david.org 写道

楼主正解，不过这题要是要求记录数组位置的话，估计就做不到 O(N) 的时间复杂度了

通过 if(nStart > nAll)  可以确定端点k，  获取nAll后从端点k顺序相加直到和等于nAll 还是O(n)

5 楼 david.org 2011-06-21  

楼主正解，不过这题要是要求记录数组位置的话，估计就做不到 O(N) 的时间复杂度了

4 楼 minipenguin 2011-06-03  

动态规划，从数组的一端开始遍历，遇到负数则置0，否则求和，遍历完答案就出来了

3 楼 chriszeng87 2011-05-29  

<div class="quote_title">Hmily49 写道</div>
<div class="quote_div">
<div class="quote_title">seedjyh 写道</div>
<div class="quote_div">
<p>典型的DP</p>
<p>计算从最左端到当前位置中最大和以及最小和，两者数列的右端点就是答案了～</p>
</div>
<br>可以说详细点么？</div>
<p>同问</p>

2 楼 Hmily49 2011-05-29  

<div class="quote_title">seedjyh 写道</div><div class="quote_div"><p>典型的DP</p>
<p>计算从最左端到当前位置中最大和以及最小和，两者数列的右端点就是答案了～</p></div><br/>可以说详细点么？

1 楼 seedjyh 2011-05-13  

<p>典型的DP</p>
<p>计算从最左端到当前位置中最大和以及最小和，两者数列的右端点就是答案了～</p>