首页 > 代码库 > POJ-2479 Maximum sum

POJ-2479 Maximum sum

2024-11-04 21:05:02   205人阅读

Maximum sum
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 34398 Accepted: 10661

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

1101 -1 2 2 3 -3 4 -4 5 -5

Sample Output

13

大致题意：给一个数列，求出数列中不想交的两个子段和，要求和最大。

思路：对于每个i来说，求出【0~i-1】的最大子段和以及【i~n-1】的最大子段和，再加起来，求最大的一个就行了。【0~i-1】的最大子段和从左向右扫描，【i~n-1】从右向左扫描即可。

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int a[50001]; 5 int left[50001]; 6 int right[50001]; 7 int main() 8 { 9     int t;10     scanf("%d",&t);11     while(t--)12     {13         int n;14         scanf("%d",&n);15         for(int i=0;i<n;i++)16             scanf("%d",&a[i]);17         left[0]=a[0];18         for(int i=1;i<n;i++)19         {20             if(left[i-1]<0)21                 left[i]=a[i];22             else23                 left[i]=left[i-1]+a[i];24         }25         for(int i=1;i<n;i++)26             left[i]=max(left[i],left[i-1]);27         right[n-1]=a[n-1];28         for(int j=n-2;j>=0;j--)29         {30             if(right[j+1]<0)31                 right[j]=a[j];32             else33                 right[j]=right[j+1]+a[j];34         }35         for(int i=n-2;i>=0;i--)36             right[i]=max(right[i+1],right[i]);37         int res=-100000000;38         for(int i=1;i<n;i++)39         {40             res=max(res,left[i-1]+right[i]);41         }42         printf("%d\n",res);43     }44     return 0;45 }
 
 
POJ-2479 Maximum sum






























        

            
                
                  
                
                

                    联系

                    我们