当前位置:网站首页>九度 1480:最大上升子序列和(动态规划思想求最值)
九度 1480:最大上升子序列和(动态规划思想求最值)
2022-07-05 10:13:00 【全栈程序员站长】
一个数的序列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; }
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/109896.html原文链接:https://javaforall.cn
边栏推荐
- AD20 制作 Logo
- 如何判断线程池已经执行完所有任务了?
- A high density 256 channel electrode cap for dry EEG
- Tianlong Babu TLBB series - questions about skill cooling and the number of attack ranges
- Fluent generates icon prompt logo widget
- isEmpty 和 isBlank 的用法区别
- Unity particle special effects series - the poison spray preform is ready, and the unitypackage package can be used directly - next
- 《剑来》语句摘录(七)
- QT VT100 parser
- 5g NR system architecture
猜你喜欢
WorkManager的学习二
@SerializedName注解使用
如何写出高质量的代码?
B站大量虚拟主播被集体强制退款:收入蒸发,还倒欠B站;乔布斯被追授美国总统自由勋章;Grafana 9 发布|极客头条...
Energy momentum: how to achieve carbon neutralization in the power industry?
非技术部门,如何参与 DevOps?
一个程序员的职业生涯到底该怎么规划?
> Could not create task ‘:app:MyTest.main()‘. > SourceSet with name ‘main‘ not found.问题修复
A large number of virtual anchors in station B were collectively forced to refund: revenue evaporated, but they still owe station B; Jobs was posthumously awarded the U.S. presidential medal of freedo
自动化规范检查软件如何发展而来?
随机推荐
如何写出高质量的代码?
The Alipay in place function can't be found, and the Alipay in place function is offline
请问postgresql cdc 怎么设置单独的增量模式呀,debezium.snapshot.mo
Swift uses userdefaults and codable to save an array of class objects or structure instances
Using directive in angualr2 to realize that the picture size changes with the window size
MySQL digital type learning notes
Unity particle special effects series - the poison spray preform is ready, and the unitypackage package can be used directly - next
Have you learned to make money in Dingding, enterprise micro and Feishu?
Learning notes 5 - high precision map solution
【Vite】1371- 手把手开发 Vite 插件
Tianlong Babu TLBB series - questions about skill cooling and the number of attack ranges
NCP1342芯片替代料PN8213 65W氮化镓充电器方案
LDAP概述
ConstraintLayout官方提供圆角ImageFilterView
Uni app running to wechat development tool cannot Preview
驱动制造业产业升级新思路的领域知识网络,什么来头?
Atcoder beginer contest 254 "e BFS" f st table maintenance differential array GCD "
Learning note 4 -- Key Technologies of high-precision map (Part 2)
一个程序员的职业生涯到底该怎么规划?
The horizontally scrolling recycleview displays five and a half on one screen, lower than the average distribution of five