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

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

        if (len == 0 || len == 1) return len;
        
        for (auto j = 0; j < len; j++) {
            for (auto i = 0; i < j; i++) {
                if(arr[i] < arr[j] && L[j] < L[i] + 1) {
                    L[j] = L[i] + 1;
                }
            }
            if (result < L[j])
                result = L[j];
        }
        return result;
    }

};