Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2407185
  • 博文数量: 392
  • 博客积分: 7040
  • 博客等级: 少将
  • 技术积分: 4138
  • 用 户 组: 普通用户
  • 注册时间: 2009-06-17 13:03
个人简介

范德萨发而为

文章分类

全部博文(392)

文章存档

2017年(5)

2016年(19)

2015年(34)

2014年(14)

2013年(47)

2012年(40)

2011年(51)

2010年(137)

2009年(45)

分类: C/C++

2011-03-14 20:06:29

F  Maximum sum
Accept:18     Submit:42
Time Limit:1000MS     Memory Limit:65536KB

Description

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

d(A)=sum{a[s1]~a[t1]}+sum{a[s2]~a[t2]}

The rule is 1<=s1<=t1

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.



思路:

1. 从左到右求最大子数组和

2. 从右到左求最大子数组和

3. 利用1,2的结果得到两个子数组的最大和

  1. #include <stdio.h>

  2. #define MAX(a, b) ((a) > (b) ? (a) : (b))

  3. int n;
  4. int data[50001];
  5. int left_max[50001];
  6. int right_max[50001];

  7. void dp_max(int *data, int *max_arr)
  8. {
  9.     int i = 0;
  10.     int sum = 0;
  11.     sum = max_arr[0] = data[0];
  12.     for (i=1; i<n; i++)
  13.     {
  14.         sum = MAX(sum + data[i], data[i]);
  15.         max_arr[i] = MAX(sum, max_arr[i-1]);
  16.     }
  17. }

  18. void reverse_arr(int *data)
  19. {
  20.     int size = n;
  21.     int front = 0;
  22.     int tail = n - 1;
  23.     int tmp = 0;

  24.     while (tail - front > 0)
  25.     {
  26.         tmp = data[front];
  27.         data[front] = data[tail];
  28.         data[tail] = tmp;
  29.         tail--;
  30.         front++;
  31.     }
  32. }

  33. void printOut(int *max_arr)
  34. {
  35.     int i;
  36.     for (i=0; i<n; i++)
  37.         printf("%d, ", max_arr[i]);
  38.     printf("\n");
  39. }

  40. int handle()
  41. {
  42.     dp_max(data, left_max);
  43.     //printOut(left_max);
  44.     reverse_arr(data);
  45.     dp_max(data, right_max);
  46.     //printOut(right_max);

  47.     int i = 0;
  48.     int tmp = 0;
  49.     int max = left_max[0] + right_max[n-2];
  50.     for (i=1; i<n-1; i++)
  51.     {
  52.         tmp = left_max[i] + right_max[n-2-i];
  53.         if (tmp > max)
  54.             max = tmp;
  55.     }

  56.     return max;
  57. }

  58. int main()
  59. {
  60.     int T = 0;
  61.     int i = 0;
  62.     int j = 0;
  63.     int ret = 0;

  64.     scanf("%d", &T);
  65.     for (i=0; i<T; i++)
  66.     {
  67.         scanf("%d", &n);
  68.         for (j=0; j<n; j++)
  69.             scanf("%d", &data[j]);
  70.         ret = handle();
  71.         printf("%d\n", ret);
  72.     }
  73. }

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