算法导论4.1-5（最大子数组问题）

练习题

已知A[1...j]的最大子数组，在线性时间内找出A[1...j+1]的最大子数组。

思路

记数组A[1...j]的最大子数组之和为M(1...j)，那么M(1...j+1)要么是M(1...j)，要么是形如[i...j+1]的子数组之和。因此只需要在线性时间求出在A[1...j]中包含A[j]的最大子数组的和SUM，比较M(1...j)与SUM+A[j+1]的大小即可。
求解SUM，需要在每次迭代中维护一个变量cur，记录上一次迭代得到的SUM，若在本次迭代中cur+A[j]<0，就将cur清零，因为之后就不需要前边得到的负数和来得到更优的SUM。

代码

#include <bits/stdc++.h>
#define rep(i,st,ed) for(int i=st;i<=ed;++i)
using namespace std;
int n,num,cur,ans=-0x3f3f3f3f;
int main()
{
	cin>>n;
	rep(i,1,n)
	{
		cin>>num;
		if(cur+num<=0)
		{
			cur=0;
			ans=max(ans,num);
		}
		else
		{
			cur+=num;
			ans=max(ans,cur);
		}
		cout<<i<<":::"<<ans<<endl;
	}
}