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
解题思路
题意：
求a1,a2,…..an这n个数的两段不相交序列的最大和。
思路：
一看就知道跟动态规划里面求最大子段和很相似，他是求两个不相交的子段，所以要分别从前往后地求出最大子段和，而要求最大子段和，就先把从第一个到后面每个数的和求出来，放在数组c[N]中，再搞个循环，更新c[i]为到第i个数的最大子段和；同理，把从后往前的最大子段和放在d[N]中。再根据sum=max{c[i]+d[i+1]} 算出最后解。
要注意的是，当只有两个数的时候要特殊输处理，直接输出他们的和，否则当有负数时会出错。
源程序
|
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 50002
#define inf -0xffff
int main()
{
int i, j, n, t, sum;
int c[N], d[N], num[N];
freopen("in.txt", "r", stdin);
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(i=1; i<=n; i++)
{
scanf("%d", &num[i]);
}
if(n == 2)
{
printf("%d\n", num[1] + num[2]);
continue;
}
memset(c, 0, sizeof(c));
memset(d, 0, sizeof(d));
c[0] = 0;
for(i=1; i<=n; i++)
{
if(c[i-1] > 0)
c[i] = c[i-1] + num[i];
else c[i] = num[i];
}
for(i=1; i<=n; i++)
{
if(c[i] < c[i-1])
c[i] = c[i-1];
}
for(i=n; i>0; i--)
{
if(d[i+1] > 0)
d[i] = d[i+1] + num[i];
else d[i] = num[i];
}
for(i=n; i>0; i--)
{
if(d[i] < d[i+1])
d[i] = d[i+1];
}
sum = inf;
for(i=1; i<=n; i++)
{
if(c[i] + d[i+1] > sum)
sum = c[i] + d[i+1];
}
printf("%d\n", sum);
}
getch();
return 0;
}
|
阅读(3185) | 评论(0) | 转发(0) |
