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

class Solution {
public:
    /**
     滚动数组
     dp[i]:以i结尾的最长上升子序列
     dp[i] = max(dp[j]+1,dp[i])
     */
    int LIS(vector<int>& arr) {
        // write code here
        int len = arr.size();
        if(len==0) return 0;
        vector<int> dp(len, 1);
        for(int i=1; i<len; i++){
            for(int j=0; j<i; j++){
                if(arr[j] < arr[i]){
                     dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        int ans=0;
        for(int i=0; i<len; i++){
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

vector<int>& arr传入的必须是一个vector地址判断为空，是根据长度，不能判断arr等于空，不同于 vector<int> arr