POJ 2479 Maximum sum 동적 계획 문제 풀이 보고서

http://poj.org/problem?id=2479
http://www.cnblogs.com/allensun/archive/2010/11/05/1870225.html
방법 1: 두 번 dp + 한 번 스 캔, 복잡 도 3 * n    최대 연속 서브 배열 을 위 한 선형 dp 알고리즘    배열 에 대해 서 는 앞으로 각각 O (n) 의 dp 를 한 번 씩 하고 maxsofar [0] [0... n - 1] 을 구하 고 배열 은 뒤에서 O (n) 의 dp 를 한 번 씩 하 며 maxsofar [1] [0... n - 1] 을 구한다.    maxsofar 를 다시 한 번 스 캔 하여 maxsofar [0] [i - 1] + maxsofar [1] [i] 의 최대 치 를 구 하 는 것 이 결과 입 니 다.   
실 현 된 코드 는 다음 과 같다.

#include<iostream>
#include<stdio.h>
#include <memory.h>
using namespace std;
const int N=50000;
int a[N];
int maxsofar[2][N];
int Max_1(int a,int b)
{
	return a>b?a:b;
}
void run_1()
{
	int t,n,val;
	int i,j;
	int maxending;
	int max;
	int sum;
	scanf("%d",&t);
	while(t--&&scanf("%d",&n))
	{
		scanf("%d",&a[0]);
		maxending=a[0];
		maxsofar[0][0]=a[0];
		for(i=1;i<n;i++)
		{
			scanf("%d",&a[i]);
			maxending=Max_1(a[i],maxending+a[i]);
			maxsofar[0][i]=Max_1(maxsofar[0][i-1],maxending);
		}
		maxending=a[n-1];maxsofar[1][n-1]=a[n-1];
		for(i=n-2;i>0;i--){
			maxending=Max_1(a[i],a[i]+maxending);
			maxsofar[1][i]=Max_1(maxsofar[1][i+1],maxending);
		}
		int max=0;
		max=maxsofar[0][n-2]+a[n-1];
		for(int i=n-2;i>0;i--)
		{
			int t=maxsofar[0][i-1]+maxsofar[1][i];
			max=max>t?max:t;
		}
		cout<<max<<endl;
	}
}
int main()
{
	run_1();
	return 0;
}

 
방법 2: dp 두 번 이면 됩 니 다.

void run()
{
	int t,n,val;
	int i,j;
	int maxending;
	int max;
	int sum;
	scanf("%d",&t);
	while(t--&&scanf("%d",&n))
	{
		scanf("%d",&a[0]);
		maxending=a[0];
		maxsofar[0][0]=a[0];
		for(i=1;i<n;i++)
		{
			scanf("%d",&a[i]);
			maxending=Max_1(a[i],maxending+a[i]);
			maxsofar[0][i]=Max_1(maxsofar[0][i-1],maxending);
		}
		maxending=a[n-1];
		maxsofar[1][n-1]=a[n-1];
		max=maxsofar[0][n-2]+a[n-1];
		for(i=n-2;i>0;--i)
		{
			maxending=Max_1(a[i],a[i]+maxending);
			maxsofar[1][i]=Max_1(maxsofar[1][i+1],maxending);
			sum=maxsofar[0][i-1]+maxsofar[1][i];
			max=max>sum?max:sum;
		}
		cout<<max<<endl;
	}
}

이상 2 단 모두 ACCEPT 시간 복잡 도 O (2 * n) 와 O (3 * n)
 

#define N 500010
int a[N];
int Cost_Left[N];//        
int Cost_Right[N];//
int Max_Left(int *a,int len)
{
	if(Cost_Left[len-2])
	{
		if(Cost_Left[len-2]+a[len-1]>Cost_Left[len-2])
		{
			Cost_Left[len-1]=Cost_Left[len-2]+a[len-1];
			return Cost_Left[len-1];
		}
		else
			return Cost_Left[len-2];
	}
	int max=0;
	int sum=0;
	for(int i=0;i<len;i++)
	{
		sum+=*(a+i);
		if(sum<0)
			sum=0;
		else
		{
			if(max<sum)
				max=sum;
		}
	}
	Cost_Left[len-1]=max;
	return max;
}
int Max_Right(int *a,int idx,int len)
{
	if(Cost_Right[len-2])
	{
		if(Cost_Right[len-2]+a[len-1]>Cost_Right[len-2])
		{
			Cost_Right[len-1]=Cost_Right[len-2]+a[len-1];
			return Cost_Right[len-1];
		}
		else
			return Cost_Right[len-2];
	}
	int max=0;
	int sum=0;
	for(int i=0;i<len;i++)
	{
		sum+=*(a+idx+i);
		if(sum<0)
			sum=0;
		else
		{
			if(max<sum)
				max=sum;
		}
	}
	return max;
}
int Max(int a[],int len)
{
	int sum=0;
	for(int i=0;i<len;i++)
	{
		int t1,t2,t;
		t1=Max_Left(a,i);
		t2=Max_Right(a,i,len-i);
		t=t1+t2;
		if(t>sum)
		{
			sum=t;
		}
	}
	return sum;
}

시간 복잡 도 O (n * n)
시간 을 초과 하 다