九度 1480:最大上升子序列和(动态规划思想求最值)

九度 1480:最大上升子序列和(动态规划思想求最值)

题目描述:

一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …,aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18,为子序列(1, 3, 5, 9)的和.

你的任务,就是对于给定的序列,求出最大上升子序列和。注意,最长的上升子序列的和不一定是最大的,比如序列(100, 1, 2, 3)的最大上升子序列和为100,而最长上升子序列为(1, 2, 3)。

 

思路

1.dp[i] 表示以 i 结尾的最大上升序列

 dp[i] = max(dp[j]) + value[i]

2. 最长上升子序列和最大上升子序列没有关系

3. 这题的思路和最大连续子数组一样

 

代码

#include <iostream> #include <stdio.h>
using namespace std; int dp[1001]; int val[1001]; int n; int main() { while(scanf("%d", &n) != EOF ) { for(int i = 0; i < n; i ++) scanf("%d", val+i); dp[0] = val[0]; for(int i = 1; i < n; i ++) { dp[i] = val[i]; for(int j = 0; j < i; j ++) { if(val[j] >= val[i]) continue; dp[i] = max(dp[i], dp[j]+val[i]); } } int resval = 0; for(int i = 0; i < n; i ++) resval = max(resval, dp[i]); cout << resval << endl; } return 0; }

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109896.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Odin Inspector 系列教程 — Value Dropdown Attribute

    Odin Inspector 系列教程 — Value Dropdown AttributeValueDropdownAttribute特性用于任何属性,并使用可配置选项创建下拉列表。使用此选项可为用户提供一组特定的选项供您选择。也就是创建一些特殊的下拉条这个里面的属性就有点多了,达到了16个!!!下面笔者逐个讲解MemberName,也是唯一一个有参构造函数需要的属性,有两种形式的Drop下拉条,一种是直接数值的,另一种是Key-Value形式的…

  • 批量下载图片

    批量下载图片

  • 5个最佳拖放式WordPress网页生成器比较(2018)

    5个最佳拖放式WordPress网页生成器比较(2018)你想要一个简单的方法来建立和定制你的WordPress网站?这就是拖放WordPress网页生成器插件派上用场的地方。这些WordPress网页生成器允许您在不编写任何代码的情况下创建、编辑和自定义您的网站布局。在本文中,我们将比较和回顾5个最好的WordPress拖放网页构建器。为什么使用拖放页面生成器的WordPress?当开始一个博客时,许多WordPress初学者发现很难在他们的网站上更改或自定义页面布局。虽然很多优质的WordPress主题都有不同的页面布局,但对于不懂HTML代码的人来说,

  • 研招网的准考证还能下载吗_考研准考证还能下载吗

    研招网的准考证还能下载吗_考研准考证还能下载吗下载打印方式往下看,有手把手教学。【考生请注意】据了解,《准考证》由考生使用A4幅面白纸在规定时间内(2021年12月10日开始至12月27日)上网自行下载打印。《准考证》正、反两面在使用期间均不得涂改或书写。考生凭下载打印的《准考证》及居民身份证参加考研初试和复试。考生凭本人《准考证》及有效居民身份证按规定时间进入考场,对号入座。入座后将上述证件放在桌面左上角,以便核验。请考生下载《准考证》前认真阅读报考点所在地省(区、市)考生防疫有关要求,并认真关注《准考证》上“省级招生考试…

  • python自动炒股软件下载_python自动股票交易软件

    python自动炒股软件下载_python自动股票交易软件获取数据是数据分析中必不可少的一部分,而网络爬虫是是获取数据的一个重要渠道之一。鉴于此,我拾起了Python这把利器,开启了网络爬虫之路。本篇使用的版本为python3.5,意在抓取证券之星上当天所有A股数据。程序主要分为三个部分:网页源码的获取、所需内容的提取、所得结果的整理。一、网页源码的获取很多人喜欢用python爬虫的原因之一就是它容易上手。只需以下几行代码既可抓取大部分网页的源码。imp…

  • 推荐几个IDEA插件,Java开发者撸码利器

    推荐几个IDEA插件,Java开发者撸码利器点击上方“Java之间”,选择“置顶或者星标”你关注的就是我关心的!来源:www.cnblogs.com/jimoer/p/8799437.html#上一篇:Java8很香但还是想升级到…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号