首页 > 代码库 > poj2479 && poj2593Maximum sum（求两个不相交最大字段的和）

poj2479 && poj2593Maximum sum（求两个不相交最大字段的和）

2024-07-11 20:41:31   220人阅读

转载请注明出处：http://blog.csdn.net/u012860063?viewmode=contents

题目链接：http://poj.org/problem?id=2479


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

Hint

In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer. 

Huge input,scanf is recommended.

Source

POJ Contest,Author:Mathematica@ZSU

代码如下：

#include <cstdio>
#include <iostream>
using namespace std;
#define INF 0x3fffffff
#define M 100000+17
int a[M],b[M];
int main()
{
	int n, i, T;
	while(~scanf("%d",&T))
	{
		while(T--)
		{
			scanf("%d",&n);
			int sum = 0, MAX = -INF;
			for(i = 1; i <= n; i++)
			{
				scanf("%d",&a[i]);
				sum+=a[i];
				if(sum > MAX)
				{
					MAX = sum;
				}
				b[i] = MAX;
				if(sum < 0)
				{
					sum = 0;
				}
			}
			MAX = -INF;
			sum = 0;
			int ans = MAX, t;
			for(i = n; i > 1; i--)
			{
				sum+=a[i];
				if(sum > MAX)
				{
					MAX = sum;
				}
				t = MAX + b[i-1];
				if(t > ans)
				{
					ans = t;
				}
				if(sum < 0)
				{
					sum = 0;
				}
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}


联系
我们