題目：

Given a sequence of K integers { N₁,N₂,...,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

解題思路：

思路參考了先前刷過的另外一道題各薇，動態(tài)規(guī)劃——買賣股票的最佳時(shí)機(jī)
這里將輸入序列的{ N₁,N₂,...,N_K }轉(zhuǎn)化為了序列A{ 0,N₁,N₁+N₂,...,N₁+N₂+...+N_K }的形式，只需算出最大的A[m]-A[j] (0≤j<m≤K)即可眼坏，此時(shí)對于原序列 [j,m)即為最大子序列所在的區(qū)間茴恰。
注意點(diǎn)——需要考慮輸入序列全為負(fù)數(shù)或全為0的特殊情況荠诬。

代碼：

編譯器：C++(g++)

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

pair<int,int> findSubseq(const vector<int> &srce)
{
    //數(shù)組全部為0的特殊情況
    for(int i=0,zero=-1;i<srce.size();++i)
    {
        if(0==srce[i]&&-1==zero)
        {
            zero=i;
        }
        if(srce[i]>0)
        {
            break;
        }
        if(i==srce.size()-1)
        {
            return make_pair(zero,zero+1);
        }
    }
    //轉(zhuǎn)換為tmp{0, srce[0], srce[0]+srce[1],..., srce[0]+...+srce[n-1]}的形式
    //若tmp[m]-tmp[j]為最大值澡为，則索引[j,m)為最大子序列
    vector<int> tmp(1,0);
    tmp.push_back(srce[0]);
    for(int i=1,n=srce[0];i<srce.size();++i)
    {
        n+=srce[i];
        tmp.push_back(n);
    }
    int minIndex=0,maxIndex=0,value=0,tmpMin=0,tmpMax=0;
    for(int i=1;i!=tmp.size();++i)
    {
        if(tmp[i]>tmp[tmpMax])
        {
            tmpMax=i;
        }
        if(tmp[i]<tmp[tmpMin]||i==tmp.size()-1)
        {
            if(tmp[tmpMax]-tmp[tmpMin]>value)
            {
                maxIndex=tmpMax;
                minIndex=tmpMin;
                value=tmp[tmpMax]-tmp[tmpMin];
            }
            tmpMax=i;
            tmpMin=i;
        }
    }
    return make_pair(minIndex,maxIndex);
}
int main()
{
    int k;
    cin>>k;
    vector<int> ivec;
    for(int i=0;i!=k;++i)
    {
        int t;
        cin>>t;
        ivec.push_back(t);
    }
    //考慮全為負(fù)值的特殊情況
    for(int i=0;i!=k;++i)
    {
        if(ivec[i]>=0)
        {
            break;
        }
        if(i==k-1)
        {
            cout<<"0 "<<ivec[0]<<" "<<ivec[i]<<endl;
            return 0;
        }
    }
    pair<int,int> ret=findSubseq(ivec);
    int sum=0;
    for(int i=ret.first;i!=ret.second;++i)
    {
        sum+=ivec[i];
    }
    cout<<sum<<" "<<ivec[ret.first]<<" "<<ivec[ret.second-1]<<endl;
    return 0;   
}