Chinaunix首页 | 论坛 | 博客
  • 博客访问: 472134
  • 博文数量: 117
  • 博客积分: 3195
  • 博客等级: 中校
  • 技术积分: 1156
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-04 01:44
文章分类

全部博文(117)

文章存档

2012年(5)

2011年(5)

2010年(46)

2009年(61)

我的朋友

分类:

2009-08-22 01:33:54

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,…..ann个数的两段不相交序列的最大和。

 

思路:

    一看就知道跟动态规划里面求最大子段和很相似,他是求两个不相交的子段,所以要分别从前往后地求出最大子段和,而要求最大子段和,就先把从第一个到后面每个数的和求出来,放在数组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;

}

阅读(3179) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~