首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >1007 Maximum Subsequence Sum

1007 Maximum Subsequence Sum

作者头像
KevinBruce
发布2020-03-12 16:07:48
4690
发布2020-03-12 16:07:48
举报
文章被收录于专栏:CTF及算法学习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行。

测试样例中可能的情况

  1. 全是负数
  2. 只有负数和零
  3. 全是整数
  4. 全是0
  5. 只有正数和0
  6. 其它

代码

#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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 题目大意
  • 思路
  • 测试样例中可能的情况
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档