1007 Maximum Subsequence Sum

KevinBruce

发布于 2020-03-12 16:07:48

5140

发布于 2020-03-12 16:07:48

文章被收录于专栏：CTF及算法学习

题目

Given a sequence of K integers {

$N_{1},N_{2},...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.

题目大意

这道题是说给你一个序列，求这个序列的最大子序列和，并按以下格式打印结果。

最大子序列和 最大子序列中第一个数 最大子序列中最后一个数

思路

这道题是一个比较典型的动态规划问题，因此确定好初状态、状态方程即可。如果使用暴力方法求解，可能会超时。该题目中初状态看输入的第一个数的值，如果是小于等于0的数，要置成0，否则置成第一个数的值。状态方程见代码的25-31行。

测试样例中可能的情况

全是负数
只有负数和零
全是整数
全是0
只有正数和0
其它

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n,flag = 1;
    cin>>n;
    vector<int>a(n,0);
    vector<int>dp(n);
    for(int i = 0;i < n;i++){
        cin>>a[i];
        if(a[i]>=0)
            flag = 0;
    }
    if(flag)
    {
        cout<<0<<" "<<a[0]<<" "<<a[n-1]<<endl;
        return 0;
    }
    //初状态
    dp[0] = max(a[0],0);
    //状态转换
    for(int i = 1;i < n;i++)
    {
        if(dp[i-1]+a[i]<0)
            dp[i] = 0;
        else
            dp[i] = dp[i-1]+a[i];
    }
    int max_pos = 0;
    for(int i = 0;i < n;i++)
        if(dp[i]>dp[max_pos])
            max_pos = i;
    if(dp[max_pos]==0)
        cout<<"0 0 0"<<endl;
    else
    {
        int tmp = max_pos;
        while (tmp>=0&&dp[tmp]>0)
            tmp--;
        cout<<dp[max_pos]<<" "<<a[tmp+1]<<" "<<a[max_pos]<<endl;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-01-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

numbers