最大上升子序列和

题目

题目链接

题解

动态规划。

dp[i]表示以第i个元素结尾的上升子序列的最大和，转移方程为dp[i] = max {a[i], dp[j] + a[i]}，最后遍历全部的i找到最大的dp值。

状态定义还是比较基础、比较常见的。

我感觉这道题不要理解成最长上升子序列的变式，而是要理解成一道基础动态规划的变式，要求子序列上升完全可以看作方程转移需要满足的要求。

代码

#include
using namespace std;

const int N = 1e5+10;

int n, ans, a[N], f[N];

int main()
{
	cin >> n;
	for (int i = 1;i > a[i];
		f[i] = a[i];
		for (int j = 1;j