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 2n 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(2n)
- Space Complexity: O(n)
DP
The equation:
dp[i]=max(dp[j])+1,0≤j<iandnums[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(n2)
- Space Complexity: 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(nlogn)
- Space Complexity: 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. 😉😃💗