【POJ2479】Maximum sum(动态规划,DP)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 03 日

跟之前的求子段最大和差不多,不知道请看http://blog.pureisle.net/?p=266
这里求的是两个子段最大和,注意看数据,两个子段均不能为空(偶在这里多两次WA)。。。。另附POJ,discuss里边别人粘贴出来了一层循环写法。。。道理都差不多,时间也差不多。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[1000001];
int res[1000001];
int main(){
	freopen("1.txt","r",stdin);
	int n,x;
	scanf("%d",&n);
	while(n--){
		scanf("%d",&x);
		int ans=-9999999,mymax=-9999999,temp=0;
		for (int i=1;i<=x;i++){
			scanf("%d",&a[i]);
			res[i]=max(res[i-1]+a[i],a[i]);
		}
		for (int i=x;i>=2;i--){
			temp +=a[i];
			if(temp>mymax) mymax=temp;
			if(ans<res[i-1]+mymax)
				ans=res[i-1]+mymax;
			if(temp<0) temp=0;
		}
		printf("%d\n",ans);
	}
}
#include<cstdio>

int max(int x, int y ) {return x>y? x : y; }

int main()
{
	int cas,n; 
	scanf("%d",&cas);
	while ( cas -- )
	{
		scanf("%d",&n);
		int a, b , ans, a_max,k; 
		a = b = a_max = 0;
		ans = -99999999;
		scanf("%d",&k);
		b = a_max = k; 
		a = max(k , 0 );
		for (int i = 1; i<n; i++)
		{
			scanf("%d",&k);
			a = a + k; 
			if ( a < 0 ) a = 0; 
			b = max( b+k , a_max+k );
			ans = max( ans , b);
			a_max = max( a, a_max);
			b = max( b , a_max);
		}
		printf("%d\n",ans);
	}
}
个人原创,转载请注明:三江小渡

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日