编程之美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保存当前的子数组之和，若为负数(最大和的子数组不可能包含当前子数组)，则在下次遍历时清零，重新寻找最大和的子数组

典型的DP

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

可以说详细点么？

同问

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

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

记录位置的话，也就是多一两句代码的问题，时间复杂度还是O（n）