首页 > 代码库 > poj 2479 max sum

poj 2479 max sum

2024-07-13 06:45:08   223人阅读

Maximum sumTime Limit:1000MS    Memory Limit:65536KB    64bit IO Format:%I64d & %I64u
SubmitStatus

Description

Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
Your task is to calculate d(A).

Input

The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.

Output

Print exactly one line for each test case. The line should contain the integer d(A).

Sample Input

1

10
1 -1 2 2 3 -3 4 -4 5 -5

Sample Output

13题意分析：求从左至右的最大的连续子序列的和然后在从右至左的一段连续子序列的和，但是这两段区间不能重叠；简单的DP：
#include<iostream>
#define max(a,b) a>b?a:b
using namespace std;
int sum[50010],dp1[50010],dp2[50010];
int a[50010];
int main()
{
  int i,j,t,n;
  int maxn;
  int N;
  cin>>N;
  while(N--)
  {
   cin>>n;
   maxn=-0x3fffffff;
   for(i=1;i<=n;i++)
   {
  scanf("%d",a+i);
   }
   sum[1]=a[1];
   dp1[1]=a[1];
   for(i=2;i<=n;i++)
   {
     sum[i]=max(sum[i-1]+a[i],a[i]);
	 maxn=max(sum[i],maxn);
	 dp1[i]=maxn;
   }
    
     maxn=-0x3fffffff;
	dp2[n]=sum[n]=a[n];
	 for(i=n-1;i>=1;i--)
	 {
	   sum[i]=max(sum[i+1]+a[i],a[i]);
	   maxn=max(maxn,sum[i]);
       dp2[i]=maxn;
	 }
    maxn=-0x3fffffff;
	for(i=1;i<n;i++)
	{
	  int temp=dp1[i]+dp2[i+1];
	  maxn=max(maxn,temp);
	}
	if(N!=1) cout<<endl;
	cout<<maxn<<endl;
  }
  return 0;
}


poj 2479 max sum


联系
我们