首页 > 代码库 > POJ-2593 Max Sequence

POJ-2593 Max Sequence

2024-11-04 22:51:39   204人阅读

Max Sequence
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 16001 Accepted: 6715

Description

Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N). 
技术分享

You should output S. 

Input

The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

Output

For each test of the input, print a line containing S.

Sample Input

5-5 9 -5 11 200

Sample Output

40

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

 1 #include <stdio.h> 2 int main() 3 { 4     int left[100005]; 5     int right[100005]; 6     int a[100005]; 7     while(1) 8     { 9         int n,i;10         scanf("%d",&n);11         if(n==0)12             break;13         for(i=0;i<n;i++)14             scanf("%d",&a[i]);15         int sumL=0;16         int max=-99999999;17         for(i=0;i<n;i++)//从左向右求到i结尾的最大连续子串的最大值    //如果这个循环看不懂的话，可以先做下hdu100318         {19             sumL=sumL+a[i];20             if(sumL>max)21                 max=sumL;22             if(sumL<0)23                 sumL=0;24             left[i]=max;25         }26         max=-99999999;27         int tmp=-99999999;28         int sumR=0;29         for(i=n-1;i>=1;i--)30         {31             sumR=sumR+a[i];32             if(sumR>max)33                 max=sumR;34             if(sumR<0)35                 sumR=0;36             if(tmp<max+left[i-1])37             tmp=max+left[i-1];38          }39          printf("%d\n",tmp);40      }41      return 0;42 }

 

POJ-2593 Max Sequence






























        

            
                
                  
                
                

                    联系

                    我们