poj 2479 和 2593 - c++编程基础

http://poj.org/problem id=2479
http://poj.org/problem id=2593
Maximum sum

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 31388		Accepted: 9627

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

Hint

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

Huge input,scanf is recommended
解题思路：

定义两个数组l[],r[]。l[k]表示下标[1...k]范围内的最大连续和，r[k]表示下标[k...n]范围内的最大连续和，

O(n)遍历k取最大即可。

2593题和该题原理一样！

#include
  
   
#include
   
     #include
    
      #include
     
       #define N 50005 const int Inf=-100000; #define Max(a,b) a>b a:b; int main() { int T,n,i,j,max; int a[N]; int l[N],r[N]; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0;i
      
       =0;i--) r[i]=Max(a[i],r[i+1]+a[i]); max=Inf; for(i=n-1;i>=0;i--) { max=Max(max,r[i]); r[i]=max; } max=Inf; for(i=0;i