题目描述
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
动态规划
主要思路是寻找以第i个数字为结尾的最长递增序列;
状态转移如下
对于第i个数结尾的最长递增序列,遍历其 之前 的所有数;
if(w[i] > w[j]) dp[i] = max(dp[j] + 1, dp[i]);
对于dp数组,全部初始化为1(如果在第i个数前没有更小的数字,则最长递增序列为1)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int M = 1010;
int n, dp[M] = {1}, res = -1;
long long w[M];
int main()
{
cin >> n;
for(int i=0; i<n; i++) cin >> w[i];
fill(dp, dp + n, 1);
for(int i=0; i<n; i++)
{
for(int j=0; j<i; j++)
{
if(w[i] > w[j]) dp[i] = max(dp[j] + 1, dp[i]);
}
res = max(res, dp[i]);
}
cout << res;
return 0;
}