算法 - 最长上升子序列

---

来源： https://www.acwing.com/problem/content/description/897/

题目描述：

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

首先要求几个东西，一个是状态状态分析，一个是状态计算。状态分析就是提出一种暴力的解决方式，然后再用DP(表格法)的方式去解决这个问题。

首先是表格的长度，因为中庸存放等长的数组，所以就只用输入长度N的一维数组就可以了，然后把f[i]和w[i]进行联系起来。所以这里就需要表示f[i]的意义了。

• 状态表示

• 集合的划分, f[i]表示： 以w[i]结尾的最长子序列，默认为1
• 属性 ： max

• 状态计算

• 也就是f[i]的划分，也就是f[i] 的计算。
• 遍历j <- 1 to i, 如果w[i] > w[j]， 更新f[i] 的值

伪代码：

res = 1
for i <- 1 to n
    for j <- 1 to i - 1
        if w[i] > w[j]
            f[i] = max(f[i], f[j] + 1)
    res = max(res, f[i])

c++ 实现：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1100;

int w[N], f[N];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];

    int res = 1;
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j < n; j++)
            if (w[i] > w[j])
                f[i] = max(f[i], f[j] + 1);

        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}