3052: 最大上升子序列和 dp做法简单秒懂

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
int main(){
    // 定义变量n和数组a、dp，其中a存储输入的数列，dp用于动态规划
    int n, a[1100], dp[1100];
    // 读取输入的数列长度n
    cin >> n;
    // 读取数列中的每个元素并初始化dp数组
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        dp[i] = a[i];
    }
    // 初始化dp数组的第一个元素
    dp[1] = a[1];
    // 动态规划计算最长递增子序列的和
    for(int i = 2; i <= n; i++){
        for(int j = 1; j < i; j++){
            // 如果a[j]小于a[i]，则更新dp[i]为dp[j]+a[i]和当前dp[i]的最大值
            if(a[j] < a[i]){
                dp[i] = max(dp[j] + a[i], dp[i]);
            }
        }
    }
    // 输出dp数组中的最大值，即最长递增子序列的和
    cout << *max_element(dp + 1, dp + n + 1) << endl;
    return 0;
}