一维情况:一个n个整数元素的一维数组(a[0],a[1],...,a[n-2],a[n-1]),求这个数组的连续子数组元素之和的最大值?
我们考虑数组的第一个元素a[0],以及最大的一段数组(a[i],...,a[j])跟a[0]之间的关系,有以下几种情况
1.当i=j=0时,元素a[0]本身构成和最大的一段;
2.当0=i<j时,和最大的一段以a[0]开始;
3.当0<i时,元素a[0]跟和最大的一段没关系
从上面三种情况可以看出,可以将一个大问题(n个元素数组)转化为一个较小的问题(n-1个元素的数组),
假设已经知道(a[1],...,a[n-1])中和最大的一段之和为all[1],并且已经知道(a[1],...,a[n-1])中包含a[1]的和最大
的一段数组的和为start[1]。那么,根据上述三种情况,不难看出(a[0],...,a[n-1])中的问题的解all[0]是三种
情况的最大值max{a[0],a[0]+start[1],all[1]}.通过这样的分析,可以看出这个问题符合无后效性,可以使用
动态规划的方法来解决。
但有一个新问题出现了:我们要额外申请了连个数组all[],start[],能否在空间方面节省一点呢?
观察连个递推式:
start[i]=max(a[i,start[i+1]+a[i]])
all[i]=max(start[i],all[i+1])
在这两个递推式中,其实只需要用两个变量就可以了。start[k+1]只有在计算start[k]时使用,而all[k+1]也只有
在计算all[k]时使用,所以只需O(1)的空间就足够了。
int maxsum(int *a,int n) { int nstart=a[n-1]; int nall=a[n-1]; for(int i=n-2;i>=0;i--) { nstart=a[i]>nstart+a[i]?a[i]:nstart+a[i]; nall=nstart>nall?nstart:nall; } return nall; }
扩展问题
如果数组a[0],...,a[n-1]首尾相邻,也就是我们允许找到一段数字(a[i],...,a[n-1],a[0],...,a[j]),请使其和最大,怎么办?
可以把问题的解分为两种情况。
1.解没有跨过a[n-1]到a[0](原问题)
2.解有跨过a[n-1]到a[0]
对于第二种情况,只要找到从a[0]开始和最大的一段(a[0],...,a[j])(0<=j<n),以及以a[n-1]结尾的和最大的一段(a[i],..a[n-1])(0<=i<n),
那么,第2种情况中,和的最大值为M_2:
M_2=a[i]+...+a[n-1]+a[0]+...+a[j]
如果i<=j,则:
M_2=a[0]+...+a[n-1]
否则
M_2=a[0]+...+a[j]+a[i]+a[n-1];
最后,再取两种情况的最大值就行了,时间复杂度为O(n).