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

Maximum Subsequence Sum

先上题目：

Maximum Subsequence Sum（25 分） Given a sequence of K integers { N​1​​ , N2​​ , …, N​K}. A continuous subsequence is defined to be { N​i​​ , N​i+1​​ , …, N​j} .where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10 -10 1 2 3 4 -5 -23 3 7 -21 Sample Output: 10 1 4

读完题后，先来想一想本题的重点：

1. 寻找序列中最大子序列和 同时表示最大子序列的初始值和结束值；
2. 当序列中所有值均小于0时，直接输出最大值为0，同时输出序列的第一个数与最后一个数；

在想一下本题有哪些解法？

第一次做这道题时，我第一想法是三个for循环（i,j，k,用i,j表示最大子序列的位置，用k确定最大值），后来和网上的大佬们比对，发现我的时间远远地大于他们。对，大佬们用的是动态规划的方式,算法复杂度就直接down down了

让我就放代码，让你们感受一下吧。

---

#include
   
    using namespace std;int a[100005];int main(){    int thismax,summax,n,startnum,endnum;//分别表示当前子序列的值，最大子序列的值，序列数，最大子序列的初始值和结束值    summax=-1;    cin>>n;    for(int i=0;i
    
     >a[i];    }    for(int i=0;i
     
      summax)            {                summax = thismax;                startnum = a[i];                endnum = a[j];            }        }    }    if(summax<=-1)    {        cout<<"0"<<" "<
      
       <<" "<
      
     
    
   

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