信息学奥赛一本通 1285：最大上升子序列和 | OpenJudge NOI 2.6 3532:最大上升子序列和

【题目链接】

ybt 1285：最大上升子序列和
OpenJudge NOI 2.6 3532:最大上升子序列和

【题目考点】

1. 动态规划：线性动规

• 最大上升子序列和

【解题思路】

1. 确定状态

分析状态：
集合：上升的子序列
限制：子序列存在的区间
属性：加和
条件：最大
统计量：加和

状态定义：
dp[i]：以第i元素为结尾的加和最大的上升子序列的加和。

2. 确定状态转移方程

记a[i]表示第i个元素

• 分割集合：以第i元素为结尾的上升子序列构成的集合。
  • 子集1：对所有满足j < i的j， 如果a[i]>a[j]，则以第j元素为结尾的上升子序列加上第i元素，形成新的上升子序列。
    此时子序列加和dp[i]为dp[j]+a[i]
  • 子集2：否则，只有一个第i元素构成上升子序列。dp[i]=a[i]

dp[i]为对所有可能的状态值中的最大值。

题目要求的是最大上升子序列的最大加和，那么就是求以每个位置为结尾的最大上升子序列的加和，即求dp数组中的最大值。

【题解代码】

解法1：线性动规

#include<bits/stdc++.h>
using namespace std;
#define N 1005
int a[N], dp[N];//dp[i]:以第i元素为结尾的加和最大的上升子序列的加和
int main()
{
    int n, mxSum = 0;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= n; ++i)
    {
        dp[i] = a[i];
        for(int j = 1; j < i; ++j)
        {
            if(a[i] > a[j])
                dp[i] = max(dp[i], dp[j]+a[i]);
        }     
    }
    for(int i = 1; i <= n; ++i)
        mxSum = max(mxSum, dp[i]);
    cout << mxSum;
    return 0;
}