Question

Formatted question description: https://leetcode.ca/all/300.html

 300	Longest Increasing Subsequence

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

 For example,
 Given [10, 9, 2, 5, 3, 7, 101, 18],
 The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.
 Note that 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?

 @tag-dp

Algorithm

First create an empty dp array, and then start to traverse the original array, for each traversed number, use binary search to find the first number not less than it in the dp array

  • If this number does not exist, add the traversed number directly after the dp array
  • If it exists, update this number to the number currently traversed, and finally return the length of the dp array
input: {4,  2, 4, 5, 3, 7}
dp[]:  {2, 3, 5, 7}

process

num: 4
i: 0
len: 1
dp[]: [4, 0, 0, 0, 0, 0]
------
num: 2
i: 0
len: 1
dp[]: [2, 0, 0, 0, 0, 0]
------
num: 4
i: 1
len: 2
dp[]: [2, 4, 0, 0, 0, 0]
------
num: 5
i: 2
len: 3
dp[]: [2, 4, 5, 0, 0, 0]
------
num: 3
i: 1
len: 3
dp[]: [2, 3, 5, 0, 0, 0]
------
num: 7
i: 3
len: 4
dp[]: [2, 3, 5, 7, 0, 0]

Code

Java

  • import java.util.Arrays;
    
    public class Longest_Increasing_Subsequence {
    
        // ref: https://leetcode.com/articles/longest-increasing-subsequence/
    
        // NlogN
        public class Solution {
            public int lengthOfLIS(int[] nums) {
    
                // store the increasing subsequence formed by including the currently encountered element
                int[] dp = new int[nums.length];
    
                int len = 0;
                for (int num : nums) {
                    // Arrays.binarySearch() method returns index of the search key, if it is contained in the array,
                    // else it returns (-(insertion point) - 1)
                    int i = Arrays.binarySearch(dp, 0, len, num);
                    if (i < 0) {
                        i = -(i + 1);
                    }
    
                    dp[i] = num;
    
                    if (i == len) {
                        len++;
                    }
                }
                return len;
            }
        }
    
        // NlogN
        public class Solution_manualBS {
            public int lengthOfLIS(int[] nums) {
    
                // store the increasing subsequence formed by including the currently encountered element
                int[] dp = new int[nums.length];
    
                int len = 0;
                for (int num : nums) {
    
                    // binary search self implementation
                    int left = 0, right = len;
                    while (left < right) {
                        int mid = left + (right - left) / 2;
                        if (dp[mid] < num) left = mid + 1;
                        else right = mid;
                    }
                    dp[right] = num;
    
                    if (right == len) {
                        len++;
                    }
                }
                return len;
            }
        }
    
        public class Solution_dp {
            public int lengthOfLIS(int[] nums) {
    
                if (nums.length == 0) {
                    return 0;
                }
    
                // dp[i] represents the length of the longest increasing subsequence possible
                //      considering the array elements upto the i-th index only,
                //      by necessarily including the i-th element
                int[] dp = new int[nums.length];
                dp[0] = 1;
    
                int longest = 1;
    
                for (int i = 1; i < dp.length; i++) {
    
                    int maxValBeforeI = 0;
    
                    for (int j = 0; j < i; j++) {
                        if (nums[i] > nums[j]) {
                            maxValBeforeI = Math.max(maxValBeforeI, dp[j]);
                        }
                    }
    
                    dp[i] = maxValBeforeI + 1;
    
                    longest = Math.max(longest, dp[i]);
                }
                return longest;
            }
        }
    
        public class Solution_recursion_with_memorization {
    
            public int lengthOfLIS(int[] nums) {
    
                // memo[i][j]memo[i][j] represents the length of the LIS possible using
                //      * nums[i] as the previous element considered to be included/not included in the LIS,
                //      * nums[j]nums[j] as the current element considered to be included/not included in the LIS.
                int memo[][] = new int[nums.length + 1][nums.length];
    
                for (int[] l : memo) {
                    Arrays.fill(l, -1);
                }
    
                return lengthofLIS(nums, -1, 0, memo);
            }
    
            public int lengthofLIS(int[] nums, int previndex, int currentIndex, int[][] memo) {
                if (currentIndex == nums.length) {
                    return 0;
                }
    
                // @note: prev+1
                if (memo[previndex + 1][currentIndex] >= 0) {
                    return memo[previndex + 1][currentIndex];
                }
    
                int taken = 0;
                if (previndex < 0 || nums[currentIndex] > nums[previndex]) {
                    taken = 1 + lengthofLIS(nums, currentIndex, currentIndex + 1, memo);
                }
    
                int nottaken = lengthofLIS(nums, previndex, currentIndex + 1, memo);
    
                // record before return
                memo[previndex + 1][currentIndex] = Math.max(taken, nottaken);
    
                return memo[previndex + 1][currentIndex];
            }
    
        }
    
    
        public class Solution_bruteForce {
    
            public int lengthOfLIS(int[] nums) {
                return lengthofLIS(nums, Integer.MIN_VALUE, 0);
            }
    
            public int lengthofLIS(int[] nums, int prev, int currentIndex) {
    
                if (currentIndex == nums.length) {
                    return 0;
                }
    
                int included = 0;
    
                if (nums[currentIndex] > prev) {
                    included = 1 + lengthofLIS(nums, nums[currentIndex], currentIndex + 1);
                }
    
                // diff is what prev is passed down
                int notIncluded = lengthofLIS(nums, prev, currentIndex + 1);
    
                return Math.max(included, notIncluded);
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/longest-increasing-subsequence/
    // Time: O(N^2)
    // Space: O(N)
    class Solution {
    public:
        int lengthOfLIS(vector<int>& A) {
            if (A.empty()) return 0;
            int N = A.size();
            vector<int> dp(N, 1);
            for (int i = 1; i < N; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (A[j] < A[i]) dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            return *max_element(begin(dp), end(dp));
        }
    };
    
  • # find the largest end element in tails that is smaller than nums[i]
    # and then replace it with nums[i] and discard the list in the same length
    # which is implemented by `tail[idx] = num`
    
    class Solution(object):
      def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tail = []
        for num in nums:
          idx = bisect.bisect_left(tail, num)
          if idx == len(tail):
            tail.append(num)
          else:
            tail[idx] = num
        return len(tail)
    
    

All Problems

All Solutions