7,最长上升子序列

 

 如果不存在就不用去求最大值了，我们只求存在的最大值

如果存在，比如上一个数是j，且a[j] < a[i]

aj ai这种情况

dp[j] + 1

所以dp[i] = max(dp[j] + 1)，需满足aj < ai，j = 0, 1, ..., i - 1

时间复杂度：n * n 

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], dp[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        dp[i] = 1; //以i结尾的上升子序列长度为1的情况，就是只有a[i]一个数 
        for (int j = 1; j < i; j++) { //枚举左边那个是哪个数 
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, dp[i]);
    }
    cout << res << endl;
    return 0;
}

 然后怎样把最长上升序列保存下来呢

我们用g数组存储一下每一个转移是怎么转移过来的

第五 二 51

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], dp[N], g[N]; 
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        dp[i] = 1; 
        g[i] = 0; //表示只有一个数 
        for (int j = 1; j < i; j++) { 
            if (a[j] < a[i]) {
                //dp[i] = max(dp[i], dp[j] + 1);
                if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    g[i] = j;
                } 
            }
        }
    }
    int k = 1; //记最优解的下标 
    for (int i = 1; i <= n; i++) {
        if (dp[k] < dp[i]) {
            k = i;
        } 
    }
    cout << dp[k] << endl;
    for (int i = 0, len = dp[k]; i < len; i++) {
        cout << a[k] << " ";
        k = g[k];
    }
    return 0;
}