题解 | #最长上升子序列(一)#

#include <vector>
class Solution {
public:
    int LIS(vector<int>& arr) {
        //先初始化一个dp数组代表到该点中最长递增子序列的长度
        //dp中的每个元素初始化为1
        //依次进行比较
        int n = arr.size();
        if(n == 1)return 1;
        if(n == 0) return 0;
        vector<int> dp(n, 1);
        int m = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            if(dp[i] > m)m = dp[i];
        }
        return m;
    }
};