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

想通了就不难，一维dp，dp[i]表示数组从0到当前下标的最长上升子序列

初始dp全为1（当前上升子序列为本身 [self]）

现在外循环i:0~n-1遍历填涂dp[i]

内循环j:0~i-1遍历下标 i 前面的上升序列数dp[j]，如果满足第j数arr[j]<第i数arr[i]，说明arr[i]可以与0-j的上升序列一起构成0-i的上升序列，当然，我们和前面的上升序列一起构成个新的自然要挑个最长的（我没有开车），即dp[i]=max(dp[i],dp[j]+1)

最后在dp数组里找到最大的就是要求的最长序列长度啦

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        vector<int>dp;
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            dp.push_back(1);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int len = 0;
        for (int i = 0; i < n; i++) {
            len = max(len, dp[i]);
        }
        return len;
    }
};