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

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

        for (int i = 1; i < arr.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i] > arr[j]) {
                    dp[i] = max(dp[i], dp[j]+1);
                    ans = max(ans, dp[i]);
                }
            }
        }

        return ans;
    }
};

dp[i]表示以下标 i 元素结尾的最长上升子序列的长度

注意：这里dp的含义是以下标 i 元素结尾（包括该元素）的最长上升子序列的长度，这样能保证递推关系的无后效性