甲级-1007 Maximum Subsequence Sum (25 分)

题目:

Given a sequence of K integers { N1,N2,...,NK }. A continuous subsequence is defined to be { Ni,Ni+1,...,Nj } 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

解题思路:

思路参考了先前刷过的另外一道题,动态规划——买卖股票的最佳时机
这里将输入序列的{ N1,N2,...,NK }转化为了序列A{ 0,N1,N1+N2,...,N1+N2+...+NK }的形式,只需算出最大的A[m]-A[j] (0≤j<m≤K)即可,此时对于原序列 [j,m)即为最大子序列所在的区间。
注意点——需要考虑输入序列全为负数或全为0的特殊情况。

代码:

编译器:C++(g++)

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

pair<int,int> findSubseq(const vector<int> &srce)
{
    //数组全部为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);
        }
    }
    //转换为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);
    }
    //考虑全为负值的特殊情况
    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;   
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目 Maximum Subsequence Sum (25)Given a sequence of K inte...
    某翁阅读 246评论 0 0
  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,449评论 0 10
  • 想好怎么过这一生了吗? 这个问题真的好难,何为人生?就是我在这浩瀚宇宙的一角慢慢走出的每一步,快不了,也慢不了。就...
    醉夏之初阅读 152评论 0 1
  • 你到底是谁 我们拥有过的生命不足以书写青春,但我们此时的生命都是书下的字字青春。 所爱隔山海,山海不可平。 海有舟...
    fxxku阅读 252评论 0 0
  • 刚查了下日历,今天是2月7号星期四,农历大年初三,在这个全国人民都不事生产的喜庆节日里,最近不事学习的我,就来...
    Sarah_Tang阅读 416评论 2 3