本文共 3284 字，大约阅读时间需要 10 分钟。

杭电刷题第四篇，这道题常规做法会出现Time Limited Exceeded，让我头痛不已。后面只能换另一种做法，才得以通过。做ACM题需要细心，更需要耐心。

原题回顾

Problem Description

Given a sequence a[1],a[2],a[3]……a[n], your job is to >calculate the max sum of a sub-sequence. For example, >given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + >5 + 4 = 14.

Input

The first line of the input contains an integer T(1<=T<=20) >which means the number of test cases. Then T lines follow, >each line starts with a number N(1<=N<=100000), then N >integers followed(all the integers are between -1000 and >1000).

Output

For each test case, you should output two lines. The first line >is “Case #:”, # means the number of the test case. The >second line contains three integers, the Max Sum in the >sequence, the start position of the sub-sequence, the end >position of the sub-sequence. If there are more than one >result, output the first one. Output a blank line between two >cases.

Sample Input

2

5 6 -1 5 4 -7

7 0 6 -1 1 -6 7 -5

Sample Output

Case 1:

14 1 4

Case 2:

7 1 6

这个题目一开始我直接使用最笨的方法，就是边累加边比较，保存最大值和数组下标，俗称“蛮力法”这个是最容易想到的方法，很不幸的是直接提交这个代码会出现超时Time Limited Exceeded，因为这个算法效率是很低的，通不过也是很正常,代码如下：

#include 
   
    using namespace std;int main(void){    int t,n,*in_num,Max_sum,tmp_num,star_pos,end_pos;    //确定case的次数    cin>>t;    if(t<1||t>20) return -1;    for(int i=1; i<=t; i++)    {        cin>>n;        if(n<1||n>100000) return -1;        in_num=new int[n];        //in_num保存数要输入的数字        for(int j=0; j
    
     >in_num[j];            if(in_num[j]<-1000||in_num[j]>1000)                 return -1;        }        //将第一个数设为最大值        Max_sum=in_num[0];        tmp_num=0;        star_pos=0;        end_pos=0;        /*思路：        我这个使用最直接的方法，先从第一个元素起一次累加比较，通过内部和比较求得一个最大子序列值，        保存他们的子序列的下标，再将该最大值和下一个元素的累加和逐个进行比较，以此类推        */        for(int k=0; k
     
      Max_sum)                {                    Max_sum=tmp_num;                    star_pos=k;                    end_pos=j;                }            }        }        cout<<"Case "<
      <<":"<
     
    
   

有了上述代码的教训，必须寻其他方法。从上面的代码分析可以看出，内部for循环效率比较低，所以要寻求代码效率更加高的算法，下面给出一个时间复杂度减少一个数量级的代码，并且Accept；

#include 
   
    using namespace std;int main(void){    int t,n,*in_num,Max_sum,tmp_sum,star_pos,end_pos;    //确定case的次数    cin>>t;    if(t<1||t>20) return -1;    for(int i=1; i<=t; i++)    {        cin>>n;        if(n<1||n>100000) return -1;        in_num=new int[n];        //in_num保存数要输入的数字        for(int j=0; j
    
     >in_num[j];            if(in_num[j]<-1000||in_num[j]>1000)                 return -1;        }        //将第一个数设为最大值        Max_sum=in_num[0];        tmp_sum=0;        int pos_tmp=0;        //这两个下标保存变量必须在每次循环内都初始化        star_pos=0;        end_pos=0;        /*思路：        先从第一个元素起累加比较，如果累加和tmp_sum从正数变为负数       说明刚加进去的数字肯定不是最大子序列里面的数。则跳过该数继续向前运算，Max_sum总是保存       着最大的子序列和，star_pos和end_pos总是与之相对应        */        for(int k=0;k
     
      Max_sum)            {                Max_sum=tmp_sum;                star_pos=pos_tmp;                end_pos=k;            }            if(tmp_sum<0)            {                tmp_sum=0;                pos_tmp=k+1;            }        }        /*控制输出部分*/        cout<<"Case "<
      <<":"<
     
    
   

可以比较上述两个代码效率，两个代码主要区别在如何累加比较的for循环里面，第二个算法更加高效。关于这两个算法的实现思路都已经写在代码注释部分，可以自己细看，不过最好还是自己动手推算相关算法一遍，更容易理解。这是一道动态规划题。

转载地址：http://bxrdb.baihongyu.com/