Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/300.html
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [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.
Example 2:
Input: nums = [0,1,0,3,2,3] Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7] Output: 1
Constraints:
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
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
-
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); } } } ############ class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int[] d = new int[n + 1]; d[1] = nums[0]; int size = 1; for (int i = 1; i < n; ++i) { if (nums[i] > d[size]) { d[++size] = nums[i]; } else { int left = 1, right = size; while (left < right) { int mid = (left + right) >> 1; if (d[mid] >= nums[i]) { right = mid; } else { left = mid + 1; } } int p = d[left] >= nums[i] ? left : 1; d[p] = nums[i]; } } return size; } } -
// 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: # if using bisect_right(tail, num), then input=[7,7,7,7,7,7,7] will output 7 but expected result is 1 idx = bisect.bisect_left(tail, num) if idx == len(tail): # same as in java: if (i == len) len++; tail.append(num) else: tail[idx] = num return len(tail) ############ class Solution: def lengthOfLIS(self, nums: List[int]) -> int: d = [nums[0]] for x in nums[1:]: if x > d[-1]: d.append(x) else: idx = bisect_left(d, x) if idx == len(d): idx = 0 d[idx] = x return len(d) -
func lengthOfLIS(nums []int) int { d := make([]int, len(nums)+1) d[1] = nums[0] size := 1 for _, x := range nums[1:] { if x > d[size] { size++ d[size] = x } else { left, right := 1, size for left < right { mid := (left + right) >> 1 if d[mid] >= x { right = mid } else { left = mid + 1 } } if d[left] < x { left = 1 } d[left] = x } } return size } -
function lengthOfLIS(nums: number[]): number { const n = nums.length; let d = new Array(n + 1); d[1] = nums[0]; let size = 1; for (let i = 1; i < n; ++i) { if (nums[i] > d[size]) { d[++size] = nums[i]; } else { let left = 1, right = size; while (left < right) { const mid = (left + right) >> 1; if (d[mid] >= nums[i]) { right = mid; } else { left = mid + 1; } } const p = d[left] >= nums[i] ? left : 1; d[p] = nums[i]; } } return size; } -
impl Solution { pub fn length_of_lis(nums: Vec<i32>) -> i32 { let n = nums.len(); let mut dp = vec![1; n]; for i in 1..n { for j in 0..i { if nums[i] > nums[j] { dp[i] = dp[i].max(dp[j] + 1); } } } *dp.iter().max().unwrap() } }