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

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