pku 2479 最大连续串和.txt

一些典型DP题的代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
#define PB push_back
//PKU 2479 最大连续串和

#define NMAX 50005
#define INFI 99999999

int shuru[NMAX];
int lsum[NMAX];//lsum[i],shuru[1..i]的最大连续串和
int rsum[NMAX];//rsum[i],shuru[i..num]的最大连续串和
int tmax[NMAX];

void cal(int num)
{
	int i,tt,zcount=0,znum,ssd=-INFI;
	for(i=1;i<=num;i++)
	{
		if(shuru[i]>0) 
		{
			zcount++;
			znum=i;
		}
	}
	if(zcount==0) 
	{	//都是负数的情况
		for(i=2;i<=num;i++)
			if(ssd<shuru[i-1]+shuru[i]) ssd=shuru[i-1]+shuru[i];
		printf("%d\n",ssd);
	}
	else if(zcount==1)
	{	//只有一个正数的情况
		if(znum==1) ssd=shuru[znum]+shuru[znum+1];
		else if(znum==num) ssd=shuru[znum-1]+shuru[znum];
		else if(shuru[znum-1]+shuru[znum]<shuru[znum]+shuru[znum+1]) ssd=shuru[znum]+shuru[znum+1];
		else ssd=shuru[znum-1]+shuru[znum];
		printf("%d\n",ssd);
	}
	else{
	lsum[0]=rsum[0]=0;
	tmax[0]=0;
	tt=0;
	for(i=1;i<=num;i++)
	{	//tmax[i]={0,tmax[i-1]+shuru[i]}
		if(tmax[i-1]+shuru[i]<0) tmax[i]=0;
		else tmax[i]=tmax[i-1]+shuru[i];
		if(tt<tmax[i]) tt=tmax[i];
		lsum[i]=tt;
	}
	tmax[num+1]=0;
	tt=0;
	for(i=num;i>=1;i--)
	{
		if(tmax[i+1]+shuru[i]<0) tmax[i]=0;
		else tmax[i]=tmax[i+1]+shuru[i];
		if(tt<tmax[i]) tt=tmax[i];
		rsum[i]=tt;
	}
	tt=0;
	for(i=1;i<num;i++)
	{	//枚举所有的分界点
		if(tt<lsum[i]+rsum[i+1]) tt=lsum[i]+rsum[i+1];
	}
	printf("%d\n",tt);
	}
}

int main()
{
	int cnum,num,j,i;
	scanf("%d",&cnum);
	for(i=1;i<=cnum;i++)
	{
		scanf("%d",&num);
		for(j=1;j<=num;j++) scanf("%d",&shuru[j]);
		cal(num);
	}
	return 0;
}