#include<iostream>
using namespace std;
int main()
{
    int num;
    cin>>num;
    while(num--)
    {
        int n;
        cin>>n;
        int a[n];
        for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
                                    //初始化
        
       int  max=a[0]+a[1];         // 通过逐一扫描最后一个选中的元素位置，得解
       int  temp1=a[0];            //0到i-2内单个最大子段
       int temp3=a[0];             // 0到i-2内以i-2为最后选中位置的单个最大子段
       int  temp2=a[0]+a[1];       //以i为最后选中元素时题目要求的两段最大值
       
        
       for(int i=2;i<n;i++)
       {    
            temp2=(temp2>temp1?temp2:temp1)+a[i];  //两种情况。是否包含i-1
              
            if(temp2>max)max=temp2;
            temp3=(temp3>0?temp3:0)+a[i-1];      //更新
            temp1=temp1>temp3?temp1:temp3;       //是否包含i-1 
      }
           
      cout<<max<<endl;      
             
   }            
                
     return 0;          
                
                
  }
    
    进一步请参阅：
              http://www.52xxyj.cn/52xxyj/blog/?action=show&id=85
                      http://www.blog.edu.cn/user3/GOLDHUANG/archives/2006/1481691.shtml
及  http://blog.csdn.net/china8848/archive/2008/01/03/2015984.aspx
我也是看了诸前辈的大作，想我的菜鸟才做出来，效率还很低，居然575ms，惭愧，希望大家一起AC改进！

    
    
    

• Re:xiexie (1395) elfin 2008-12-10 22:15:31
• 左右各求一次最大子段和并记录每个点的情况O（n），然后扫描一次O（n） (5) cyacm 2008-12-12 20:51:06
  • Re:正是如此 2次dp即可 (2) tzkq 2008-12-21 22:40:43
  • Re:左右各求一次最大子段和并记录每个点的情况O（n），然后扫描一次O（n） (9) ainizhouni 2009-07-21 16:36:11
• Re:终于过了，好像可以o（n） (1477) chenyukang 2009-07-15 23:20:19
  • Re:终于过了，好像可以o（n） (395) angeladjx 2009-07-18 16:28:19