poj2479

maksyuki 发表于 oj 分类，标签:
15 9月 2015
0

Maximum sum

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

 

题目类型：最大连续子序列和

算法分析：假设所求两个子序列最大和为sum,两个子序列分别为left和right，这两个子段一个在序列的左边，一个在右边。那么在它们中间必定有一个分割点(这个点即可能被包含在其中一个子段中，也可能不)。设这个点为k，那么left必定是从0到k这个子段的最大子序列(用反证法证明，假设存在在0到k这个范围内的一个子序列nleft的比left大，那么nleft+right将大于sum,这就与上面假设最和为sum矛盾，所以必定不成立比left大的nleft)

，right必定是从k+1到n-1(n为序列长度)这个子段的最大子序列(证明过程同上)，那么我们现在的问题就转换成了求两个最大子序列。我们从左边开始，往右边求出每个点的最大左子段和，保存在Left数组中，然后再从右边开始，往左边求出每个点的最大右子段和，然后再遍历每个点，求出每个点的两个最大左右子段和，即可得出答案。

注意：由于求最大子序列和的全局最优解需要遍历一下数组dp，这里使用就地滚动来将dp[i-1]的最优解和dp[i]处的最优解进行比较，选取更优的存储在dp[i]中，则此时dp[i]数组中存储的是前i个数组成的最大子序列和