当前位置:网站首页>[dynamic programming] Ji Suan Ke: Suan tou Jun breaks through the barrier (variant of the longest increasing subsequence)
[dynamic programming] Ji Suan Ke: Suan tou Jun breaks through the barrier (variant of the longest increasing subsequence)
2022-07-03 21:57:00 【muse_ age】
The question : Find the maximum value of the sum of increasing subsequences
dp[i]: With nums[i] The maximum value of the sum of increasing subsequences at the end
initialization : dp[0]=nums[0]
State transition equation : dp[i]=max{dp[j]}+num[i] if(nums[j]<nums[i]) 0<=j<i
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int nums[100];
for(int i=0;i<n;i++){
cin>>nums[i];
}
int dp[100];
for(int i=0;i<n;i++)
dp[i]=nums[i];
int res=0;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[j]<nums[i])
dp[i]=max(dp[i],dp[j]+nums[i]);
res=max(res,dp[i]);
}
}
cout<<res;
}
边栏推荐
- Great gods, I want to send two broadcast streams: 1. Load basic data from MySQL and 2. Load changes in basic data from Kafka
- Nacos common configuration
- [vulnhub shooting range] impulse: lupinone
- Leetcode problem solving - 230 The k-th smallest element in the binary search tree
- 使用dnSpy對無源碼EXE或DLL進行反編譯並且修改
- MySQL——JDBC
- China's coal industry investment strategic planning future production and marketing demand forecast report Ⓘ 2022 ~ 2028
- Pengcheng cup Web_ WP
- Capturing and sorting out external articles -- autoresponder, composer, statistics [III]
- Under the double reduction policy, research travel may become a big winner
猜你喜欢
[SRS] build a specified version of SRS
Implementation principle of inheritance, encapsulation and polymorphism
Exclusive interview with the person in charge of openkruise: to what extent has cloud native application automation developed now?
Compilation Principle -- syntax analysis
Persistence of Nacos
How PHP adds two numbers
Advanced technology management - how to examine candidates in the interview and increase the entry probability
MySQL——索引
Asynchronous artifact: implementation principle and usage scenario of completable future
The latest analysis of crane driver (limited to bridge crane) in 2022 and the test questions and analysis of crane driver (limited to bridge crane)
随机推荐
JS Demo calcule combien de jours il reste de l'année
JS notes (III)
股票炒股开户注册安全靠谱吗?有没有风险的?
Bluebridge cup Guoxin Changtian single chip microcomputer -- hardware environment (I)
The 14th five year plan for the construction of Chinese Enterprise Universities and the feasibility study report on investment Ⓓ 2022 ~ 2028
Notes on MySQL related knowledge points (startup, index)
DOM light switch case
Capturing and sorting out external articles -- autoresponder, composer, statistics [III]
Getting started with postman -- built-in dynamic parameters, custom parameters and assertions
JS demo calculate how many days are left in this year
gslb(global server load balance)技术的一点理解
How PHP gets all method names of objects
Service discovery and load balancing mechanism -service
2022 G3 boiler water treatment registration examination and G3 boiler water treatment examination papers
MySQL - SQL injection problem
内存分析器 (MAT)
17 websites for practicing automated testing. I'm sure you'll like them
Day 9 HomeWrok-ClassHierarchyAnalysis
Décompiler et modifier un exe ou une DLL non source en utilisant dnspy
Supply and demand situation and market scale calculation report of China's portable energy storage power PES industry Ⓛ 2022 ~ 2028