NOJ1142-最大连续和

最大连续和

时间限制(普通/Java) : 1000 MS/ 3000 MS          运行内存限制 : 65536 KByte
总提交 : 1282            测试通过 : 230 

比赛描述

给出一个长度为n的序列A1，A2，…，An，求最大的连续和。要求找到1≤i≤j ≤n，使得Ai+Ai+1+…+Aj尽量大。

输入

第1行输入一个正整数n（n≤1000），此后输入n行，每行给出一个测试用例，包含正整数m和m个整数，以空格分隔各个数。

输出

输出n行。对于每一个测试用例，在一行输出最大的连续和。

样例输入

2
3 1 -1 3
3 1 2 3

样例输出

3
6

题目来源

刘汝佳《算法竞赛入门经典》

思路：好多OJ上都有这道题，也算是个典型问题吧~~如果要枚举是不可行的，会超时。递推效率会提高但也会超时。最好的还是递归分治没有超时。在蓝桥杯的OJ上也有这道题，同样三种思路测了一下，前两种都是超时的。

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #define MAX 100000 + 10

 using namespace std;

 int A[MAX];

 int maxsum( int *A, int x, int y )

 {

     int v, L, R, max;

     if( y - x ==  )    return A[x];

     int m = x + ( y - x ) /;

     int maxs = std::max( maxsum( A, x, m ), maxsum( A, m, y ) );

     v = ;

     L = A[m - ];

     for( int i = m - ; i >= x; i-- )

         L = std::max( L, v += A[i] );

     v = ;

     R = A[m];

     for( int i = m; i < y; i++ )

         R = std::max( R, v += A[i] );

     return std::max( maxs, L + R );

 }

 int main()

 {

     int n, i;

     scanf( "%d", &n );

     //char ch;

     while( n >  ) {

         int m;

         scanf( "%d", &m );

         for( i = ; i < m; i++ ) {

             scanf( "%d", &A[i] );

         }

         int sum = maxsum( A, , m );

         printf( "%d\n", sum );

         n--;

     }

     return ;

 }