当前位置:网站首页>Nine degrees 1480: maximum ascending subsequence sum (dynamic programming idea for the maximum value)
Nine degrees 1480: maximum ascending subsequence sum (dynamic programming idea for the maximum value)
2022-07-05 10:33:00 【Full stack programmer webmaster】
A sequence of numbers bi, When b1 < b2 < … < bS When , We call this sequence ascending . For a given sequence (a1, a2, …,aN), We can get some ascending subsequences (ai1, ai2, …, aiK), here 1 <= i1 < i2 < … < iK <= N. such as , For the sequence (1, 7, 3, 5, 9, 4, 8), It has some ascending subsequences , Such as (1, 7), (3, 4, 8) wait . The maximum sum of these subsequences is 18, For subsequences (1, 3, 5, 9) And .
Your task , For a given sequence , Find the maximum ascending subsequence and . Be careful , The sum of the longest ascending subsequence is not necessarily the largest , Example sequence (100, 1, 2, 3) The maximum sum of ascending subsequences is 100, The longest ascending subsequence is (1, 2, 3).
Ideas
1.dp[i] Said to i Maximum ascending sequence at the end
dp[i] = max(dp[j]) + value[i]
2. There is no relationship between the longest ascending subsequence and the largest ascending subsequence
3. The idea of this problem is the same as that of the largest continuous subarray
Code
#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; }
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/109896.html Link to the original text :https://javaforall.cn
边栏推荐
- The most complete is an I2C summary
- IDEA新建sprintboot项目
- Error: module not found: error: can't resolve 'xxx' in 'XXXX‘
- La vue latérale du cycle affiche cinq demi - écrans en dessous de cinq distributions moyennes
- C语言实现QQ聊天室小项目 [完整源码]
- Z-blog template installation and use tutorial
- [observation] with the rise of the "independent station" model of cross-border e-commerce, how to seize the next dividend explosion era?
- 重磅:国产IDE发布,由阿里研发,完全开源!
- How to plan the career of a programmer?
- 《通信软件开发与应用》课程结业报告
猜你喜欢
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
What is the most suitable book for programmers to engage in open source?
Workmanager learning 1
"Everyday Mathematics" serial 58: February 27
Usage differences between isempty and isblank
【黑马早报】罗永浩回应调侃东方甄选;董卿丈夫密春雷被执行超7亿;吉利正式收购魅族;华为发布问界M7;豆瓣为周杰伦专辑提前开分道歉...
Ad20 make logo
伪类元素--before和after
Today in history: the first e-book came out; The inventor of magnetic stripe card was born; The pioneer of handheld computer was born
非技術部門,如何參與 DevOps?
随机推荐
DDOS攻击原理,被ddos攻击的现象
LiveData 面试题库、解答---LiveData 面试 7 连问~
LDAP概述
请问postgresql cdc 怎么设置单独的增量模式呀,debezium.snapshot.mo
【黑马早报】罗永浩回应调侃东方甄选;董卿丈夫密春雷被执行超7亿;吉利正式收购魅族;华为发布问界M7;豆瓣为周杰伦专辑提前开分道歉...
Completion report of communication software development and Application
报错:Module not found: Error: Can‘t resolve ‘XXX‘ in ‘XXXX‘
Have the bosses ever encountered such problems in the implementation of flinksql by Flink CDC mongdb?
What are the top ten securities companies? Is it safe to open an account online?
@Serializedname annotation use
Flink CDC cannot monitor MySQL logs. Have you ever encountered this problem?
SLAM 01.人类识别环境&路径的模型建立
Should the dependency given by the official website be Flink SQL connector MySQL CDC, with dependency added
@SerializedName注解使用
Learning notes 5 - high precision map solution
C#实现获取DevExpress中GridView表格进行过滤或排序后的数据
C language QQ chat room small project [complete source code]
【js学习笔记五十四】BFC方式
Z-blog template installation and use tutorial
面试:Bitmap像素内存分配在堆内存还是在native中