Welcome to Subscribe On Youtube
300. Longest Increasing Subsequence
Description
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?
Solutions
Dynamic programming or Binary Indexed Tree.
DP
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]
-
class Solution { public int lengthOfLIS(int[] nums) { int[] s = nums.clone(); Arrays.sort(s); int m = 0; int n = s.length; for (int i = 0; i < n; ++i) { if (i == 0 || s[i] != s[i - 1]) { s[m++] = s[i]; } } BinaryIndexedTree tree = new BinaryIndexedTree(m); for (int x : nums) { x = search(s, x, m); int t = tree.query(x - 1) + 1; tree.update(x, t); } return tree.query(m); } private int search(int[] nums, int x, int r) { int l = 0; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l + 1; } } class BinaryIndexedTree { private int n; private int[] c; public BinaryIndexedTree(int n) { this.n = n; c = new int[n + 1]; } public void update(int x, int v) { while (x <= n) { c[x] = Math.max(c[x], v); x += x & -x; } } public int query(int x) { int mx = 0; while (x > 0) { mx = Math.max(mx, c[x]); x -= x & -x; } return mx; } } -
class BinaryIndexedTree { public: BinaryIndexedTree(int _n) : n(_n) , c(_n + 1) {} void update(int x, int v) { while (x <= n) { c[x] = max(c[x], v); x += x & -x; } } int query(int x) { int mx = 0; while (x) { mx = max(mx, c[x]); x -= x & -x; } return mx; } private: int n; vector<int> c; }; class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> s = nums; sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); BinaryIndexedTree tree(s.size()); for (int x : nums) { x = lower_bound(s.begin(), s.end(), x) - s.begin() + 1; int t = tree.query(x - 1) + 1; tree.update(x, t); } return tree.query(s.size()); } }; -
# 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) # implementation of bisect.bisect_left() # similar to Leetcode-302, find left/right/top/bottom callable def bisect_left(a, x, lo=0, hi=None): if hi is None: hi = len(a) while lo < hi: mid = (lo + hi) // 2 if a[mid] < x: lo = mid + 1 else: hi = mid return lo ############ class BinaryIndexedTree: def __init__(self, n: int): self.n = n self.c = [0] * (n + 1) def update(self, x: int, v: int): while x <= self.n: self.c[x] = max(self.c[x], v) x += x & -x def query(self, x: int) -> int: mx = 0 while x: mx = max(mx, self.c[x]) x -= x & -x return mx class Solution: def lengthOfLIS(self, nums: List[int]) -> int: s = sorted(set(nums)) m = len(s) tree = BinaryIndexedTree(m) for x in nums: x = bisect_left(s, x) + 1 t = tree.query(x - 1) + 1 tree.update(x, t) return tree.query(m) -
type BinaryIndexedTree struct { n int c []int } func newBinaryIndexedTree(n int) *BinaryIndexedTree { return &BinaryIndexedTree{n, make([]int, n+1)} } func (bit *BinaryIndexedTree) update(x, v int) { for x <= bit.n { bit.c[x] = max(bit.c[x], v) x += x & -x } } func (bit *BinaryIndexedTree) query(x int) int { mx := 0 for x > 0 { mx = max(mx, bit.c[x]) x -= x & -x } return mx } func lengthOfLIS(nums []int) int { n := len(nums) s := make([]int, n) copy(s, nums) sort.Ints(s) m := 0 for i, x := range s { if i == 0 || x != s[i-1] { s[m] = x m++ } } tree := newBinaryIndexedTree(m) for _, x := range nums { x = sort.SearchInts(s[:m], x) + 1 t := tree.query(x-1) + 1 tree.update(x, t) } return tree.query(m) } -
class BinaryIndexedTree { private n: number; private c: number[]; constructor(n: number) { this.n = n; this.c = new Array(n + 1).fill(0); } update(x: number, v: number) { while (x <= this.n) { this.c[x] = Math.max(this.c[x], v); x += x & -x; } } query(x: number): number { let mx = 0; while (x) { mx = Math.max(mx, this.c[x]); x -= x & -x; } return mx; } } function lengthOfLIS(nums: number[]): number { const s = [...new Set(nums)].sort((a, b) => a - b); const m = s.length; const tree = new BinaryIndexedTree(m); for (let x of nums) { x = search(s, x); const t = tree.query(x - 1) + 1; tree.update(x, t); } return tree.query(m); } function search(nums: number[], x: number): number { let l = 0, r = nums.length - 1; while (l < r) { const mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l + 1; } -
impl Solution { pub fn length_of_lis(nums: Vec<i32>) -> i32 { let n = nums.len(); let mut f = vec![1; n]; for i in 1..n { for j in 0..i { if nums[j] < nums[i] { f[i] = f[i].max(f[j] + 1); } } } *f.iter().max().unwrap() } }