当前位置:网站首页>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
边栏推荐
- How did automated specification inspection software develop?
- Implementation of wechat applet bottom loading and pull-down refresh
- 一个程序员的职业生涯到底该怎么规划?
- > Could not create task ‘:app:MyTest.main()‘. > SourceSet with name ‘main‘ not found.问题修复
- The Alipay in place function can't be found, and the Alipay in place function is offline
- 如何写出高质量的代码?
- Glide conclusion
- C#实现获取DevExpress中GridView表格进行过滤或排序后的数据
- Qt实现json解析
- WorkManager的学习二
猜你喜欢
随机推荐
Learning II of workmanager
Interview: is bitmap pixel memory allocated in heap memory or native
小程序中自定义行内左滑按钮,类似于qq和wx消息界面那种
Personal website construction tutorial | local website environment construction | website production tutorial
Node の MongoDB Driver
Idea create a new sprintboot project
[可能没有默认的字体]Warning: imagettfbbox() [function.imagettfbbox]: Invalid font filename……
MFC宠物商店信息管理系统
How to judge that the thread pool has completed all tasks?
SLAM 01.人类识别环境&路径的模型建立
【Vite】1371- 手把手开发 Vite 插件
Solution of ellipsis when pytorch outputs tensor (output tensor completely)
IDEA新建sprintboot项目
uniapp + uniCloud+unipay 实现微信小程序支付功能
Shortcut keys for vscode
> Could not create task ‘:app:MyTest.main()‘. > SourceSet with name ‘main‘ not found.问题修复
Z-blog template installation and use tutorial
各位大佬,我测试起了3条线程同时往3个mysql表中写入,每条线程分别写入100000条数据,用了f
GO项目实战 — Gorm格式化时间字段
面试:List 如何根据对象的属性去重?