By Long Luo
This article is the solution 3 Approaches: Backtrack, DP, Binary Search of Problem 300. Longest Increasing Subsequence .
Here shows 3 Approaches to slove this problem: Backtrack, DP , Binary Search .
Backtrack
The Brute Force approach, there are 2 n 2^n 2 n subsequences, use Backtrack to find the answer.
TLE!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { int minCount = Integer.MAX_VALUE; public int coinChange (int [] coins, int amount) { if (amount <= 0 ) { return 0 ; } minCount = Integer.MAX_VALUE; dfs(coins, amount, 0 ); return minCount == Integer.MAX_VALUE ? -1 : minCount; } private int dfs (int [] coins, int remain, int count) { if (remain < 0 ) { return -1 ; } if (remain == 0 ) { minCount = Math.min(minCount, count); return count; } for (int x : coins) { dfs(coins, remain - x, count + 1 ); } return -1 ; } }
Analysis
Time Complexity : O ( 2 n ) O(2^n) O ( 2 n )
Space Complexity : O ( n ) O(n) O ( n )
DP
The equation:
d p [ i ] = max ( d p [ j ] ) + 1 , 0 ≤ j < i a n d nums [ j ] < nums [ i ] dp[i] = \textit{max}(dp[j]) + 1, 0 \leq j < i and \textit{nums}[j] < \textit{nums}[i] d p [ i ] = max ( d p [ j ] ) + 1 , 0 ≤ j < i a n d nums [ j ] < nums [ i ] .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int lengthOfLIS (int [] nums) { int len = nums.length; if (len <= 1 ) { return len; } int max = 1 ; int [] dp = new int [len]; Arrays.fill(dp, 1 ); for (int i = 1 ; i < len; i++) { for (int j = 0 ; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1 ); } } max = Math.max(max, dp[i]); } return max; } }
Analysis
Time Complexity : O ( n 2 ) O(n^2) O ( n 2 )
Space Complexity : O ( n ) O(n) O ( n )
Binary Search
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public int lengthOfLIS (int [] nums) { int len = nums.length; if (len <= 1 ) { return len; } int [] tail = new int [len]; tail[0 ] = nums[0 ]; int maxLen = 1 ; for (int i = 1 ; i < len; i++) { if (nums[i] > tail[maxLen - 1 ]) { tail[maxLen] = nums[i]; maxLen++; } else { int left = 0 ; int right = maxLen - 1 ; while (left < right) { int mid = left + (right - left) / 2 ; if (tail[mid] < nums[i]) { left = mid + 1 ; } else { right = mid; } } tail[left] = nums[i]; } } return maxLen; } }
Analysis
Time Complexity : O ( n l o g n ) O(nlogn) O ( n l o g n )
Space Complexity : O ( n ) O(n) O ( n )
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗