A typical O(n^2) solution uses dynamic programming. Let's use lens[j] to denote the length of the LIS ending with nums[j]. The state equations are

lens[0] = 1

lens[j] = max_{i = 0, 1, 2, ..., j - 1}(lens[j], lens[i] + 1)

Then the length of the LIS of nums is just the maximum value in lens. The code is as follows.

1 class Solution { 2 public: 3     int lengthOfLIS(vector
     
      & nums) { 4         if (nums.empty()) return 0; 5         int n = nums.size(), ml = 1; 6         vector
      
        lens(n, 1); 7         for (int j = 1; j < n; j++) { 8             for (int i = 0; i < j; i++) 9                 if (nums[j] > nums[i])10                     lens[j] = max(lens[j], lens[i] + 1);11             ml = max(ml, lens[j]);12         }13         return ml;14     }15 };
      
     

The O(nlogn) solution is much more complicated. Try to read through the explanation of it in first. The code is as follows.

class Solution {public:    int lengthOfLIS(vector
     
      & nums) {        if (nums.empty()) return 0;        vector
      
        ends{nums[0]};        for (int num : nums) {            if (num < ends[0]) ends[0] = num;            else if (num > ends.back()) ends.push_back(num);            else {                int l = 0, r = ends.size() - 1;                while (l < r) {                    int m = l + (r - l) / 2;                    if (ends[m] < num) l = m + 1;                    else r = m;                }                ends[r] = num;            }        }        return ends.size();    }};
      
     

If you look at the else part carefully, you may notice that it can be done using lower_bound. So we will have a much shorter code, like .

1 class Solution { 2 public: 3     int lengthOfLIS(vector
     
      & nums) { 4         vector
      
        ends; 5         for (int num : nums) { 6             auto it = lower_bound(ends.begin(), ends.end(), num); 7             if (it == ends.end()) ends.push_back(num); 8             else *it = num; 9         }10         return ends.size();11     }12 };