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

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

        return res;
    }
};