try_Leetcode/300_Longest_Increasing_Subsequence.cpp at master · watchingthewheelsgo/try_Leetcode · GitHub

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    // dp/ O(n^2)
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        vector<int> f(n, 1);
        for (int i=0; i<n; ++i) {
            for (int j=0; j<i; ++j) {
                if (nums[i] > nums[j]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        return *max_element(f.begin(), f.end());
    }
    // smarter method. O(nlogn)

    // int lengthOfLIS(vector<int>& nums) {
    //     if (nums.empty())
    //         return 0;
    //     vector<int> s;
    //     s.push_back(nums[0]);
    //     for (int i=0; i<nums.size(); ++i) {
    //         auto pos = lower_bound(s.begin(), s.end(), nums[i]);
    //         if (pos == s.end())
    //             s.push_back(nums[i]);
    //         else
    //             *pos = nums[i];
    //     }
    //     return s.size();
    // }

// O(nlogn). lower_bound implemented by getUp().

//     int getUp(vector<int> &s, int k) {
//         int l=-1,r=s.size()-1;
//         while (r-l>1) {
//             int m=l+(r-l)/2;
//             if (s[m] >= k)
//                 r=m;
//             else
//                 l=m;
//         }
//         return r;
//     }
//     int lengthOfLIS(vector<int>& nums) {
//         if (nums.empty())
//             return 0;
//         vector<int> s;
//         s.push_back(nums[0]);
//         for (int i=0; i<nums.size(); ++i) {
//             if (nums[i] < s[0])
//                 s[0] = nums[i];
//             else if (nums[i] > s[s.size()-1])
//                 s.push_back(nums[i]);
//             else
//                 s[getUp(s,nums[i])] = nums[i];
//         }
//         return s.size();

//     }
};