POJ 2479 && POJ 2593

考え方:この問題は2つの交差しないサブセグメントの最大サブセグメント和を求め,しかもO(n)のアルゴリズムしか使えず,他はタイムアウトするので,解題の主な考え方はDPである.
まず左右からDPを用いて最大のサブセグメント和を求め,主なアルゴリズム:

for(i=0; i<n; i++){
	scanf("%d",&s[i]);
	sum += s[i];
	if(sum > temp){
		temp = sum;
	}
	dp[i] = temp;
	if(sum < 0){
	sum = 0;
	}
}

 
次に、2つの交差しないサブセグメントの最大和を右から左に求めます.
すべてのコード:

#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
	int s[100001];
	int dp[100001];
	int i,j,n,temp,c,sum,ans;
	while(cin>>n){
		if(n == 0) return 0;
		sum = 0;
		temp = INT_MIN;
		for(i=0; i<n; i++){
			scanf("%d",&s[i]);
			sum += s[i];
			if(sum > temp){
				temp = sum;
			}
			dp[i] = temp;
			if(sum < 0){
				sum = 0;
			}
		}
		sum = 0;
		ans = temp = INT_MIN;
		for(i=n-1; i>0; i--){
			sum += s[i];
			if(sum > temp){
				temp = sum;
			}
			if(dp[i-1] + temp > ans){
				ans = dp[i-1] + temp;
			}
			if(sum < 0 ) sum = 0;
		}
		cout<<ans<<endl;
	}
	return 0;
}