[线性dp]最大上升子序列和(最长上升子序列模型+经典)

0. 前言

相关&＃xff1a;

[线性dp] 最长上升子序列(模板题&＃43;最长上升子序列模型)

1. LIS 变种&＃43;经典变种

1016. 最大上升子序列和

本题很考思维抽象。

重点&＃xff1a; 线性 dp、LIS 问题、思维抽象

思路&＃xff1a;

• 状态定义&＃xff1a;
  • f[i] 表示所有以 a[i] 结尾的上升子序列和的最大值
• 状态转移&＃xff1a;
  • 分类依据&＃xff1a;倒数第二个数是哪个数&＃xff0c;可将状态分类为倒数第二个数为空、为a[1]、a[2]、...、a[i-1]&＃xff0c;总共是有 i 种情况&＃xff0c;假设倒数第二个数是 a[k] 的话&＃xff1a;
    • 当 a[i] > a[k] 时发生状态转移&＃xff0c;有 f[i] &＃61; max(f[i], f[k] &＃43; a[i])&＃xff0c;k &＃61; 0, 1, 2,...,i-1
• 状态转移方程&＃xff1a; f[i] &＃61; max(f[i], f[k] &＃43; a[i])&＃xff0c;k &＃61; 0, 1, 2,...,i-1

就是把求 LIS 状态转移方程的 &＃43;1 操作变成了 &＃43;a[i]&＃xff0c;就行了。

就从状态定义、集合划分角度考虑问题就行了。也没必要太纠结像不像的。

代码&＃xff1a;

#include
#include using namespace std;const int N &＃61; 1e3&＃43;5;int n;
int a[N];
int f[N];int main() {cin >> n;for (int i &＃61; 0; i < n; &＃43;&＃43;i) cin >> a[i];for (int i &＃61; 0; i < n; &＃43;&＃43;i) {f[i] &＃61; a[i];for (int j &＃61; 0; j < i; &＃43;&＃43;j)if (a[i] > a[j])f[i] &＃61; max(f[i], f[j] &＃43; a[i]);}int res &＃61; 0;for (int i &＃61; 0; i < n; &＃43;&＃43;i) res &＃61; max(res, f[i]);cout << res << endl;return 0;
}