300. Longest Increasing Subsequence.md

300. Longest Increasing Subsequence

---

Difficulty : Medium

Related Topics : Binary Search、Dynamic Programming

---

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

---

Solution

• mine
  • Java
    • DP Runtime: 13 ms, faster than 33.13%, Memory Usage: 37.4 MB, less than 57.52% of Java online submissions

      // O(N^2)time  
      // O(N) space
      public int lengthOfLIS(int[] nums) {
          int l = 0;
          if(nums == null || (l = nums.length) < 2){
              return l; 
          }
          int[] dp = new int[l];
          Arrays.fill(dp, 1);
          int res = 1;
          for(int i = 1; i < l; i++){
              for(int j = 0; j < i; j++){
                  if(nums[j] < nums[i]){
                      dp[i] = Math.max(dp[i], dp[j] + 1);
                  }
              }
              res = Math.max(res, dp[i]);
          }
          return res;
      }
      

---

• the most votes

• Greedy & Binary Search Runtime: 1 ms, faster than 87.92%, Memory Usage: 37.1 MB, less than 95.00% of Java online submissions

  // O(N*logN) time   
  // O(N) space
  public int lengthOfLIS(int[] nums) {
      int[] tails = new int[nums.length];
      int size = 0;
      for (int x : nums) {
          int i = 0, j = size;
          while (i != j) {
              int m = (i + j) / 2;
              if (tails[m] < x)
                  i = m + 1;
              else
                  j = m;
          }
          tails[i] = x;
          if (i == size) ++size;
      }
      return size;
  }
  

---