最长上升子序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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