Nine degrees 1480: maximum ascending subsequence sum (dynamic programming idea for the maximum value)

Title Description ：

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; }

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/109896.html Link to the original text ：https://javaforall.cn