|
4 | 4 |
|
5 | 5 | publicclass_300 { |
6 | 6 |
|
| 7 | +/** |
| 8 | + * credit: https://leetcode.com/problems/longest-increasing-subsequence/solution/ |
| 9 | + */ |
7 | 10 | publicstaticclassSolution1 { |
| 11 | +/** |
| 12 | + * brute force: |
| 13 | + * Time: O(2^n), size of recursion tree will be: 2^n |
| 14 | + * Space: O(n^2) |
| 15 | + * will result in Time Limit Exceeded exception. |
| 16 | + * <p> |
| 17 | + * The idea is straightforward: we'll iterate through each number, check to see if its next neighbor is smaller or bigger than itself, |
| 18 | + * if bigger, then we'll take it, if not, we'll not take it. |
| 19 | + */ |
| 20 | +publicintlengthOfLIS(int[]nums) { |
| 21 | +returnrecursion(nums,Integer.MIN_VALUE,0); |
| 22 | + } |
| 23 | + |
| 24 | +privateintrecursion(int[]nums,intprev,intcurr) { |
| 25 | +if (curr ==nums.length) { |
| 26 | +return0; |
| 27 | + } |
| 28 | +inttaken =0; |
| 29 | +if (nums[curr] >prev) { |
| 30 | +taken =1 +recursion(nums,nums[curr],curr +1); |
| 31 | + } |
| 32 | +intnotTaken =recursion(nums,prev,curr +1); |
| 33 | +returnMath.max(taken,notTaken); |
| 34 | + } |
| 35 | + } |
| 36 | + |
| 37 | +publicstaticclassSolution2 { |
| 38 | +/** |
| 39 | + * This is an iteration on the previous solution, we use a 2-d array to memoize the previously calculated result |
| 40 | + * Time: O(n^2) |
| 41 | + * Space: O(n^2) |
| 42 | + */ |
| 43 | +publicintlengthOfLIS(int[]nums) { |
| 44 | +intlen =nums.length; |
| 45 | +int[][]memo =newint[len +1][len]; |
| 46 | +for (int[]m :memo) { |
| 47 | +Arrays.fill(m, -1); |
| 48 | + } |
| 49 | +returnrecusionWithMemo(nums, -1,0,memo); |
| 50 | + } |
| 51 | + |
| 52 | +privateintrecusionWithMemo(int[]nums,intprevIndex,intcurrIndex,int[][]memo) { |
| 53 | +if (currIndex ==nums.length) { |
| 54 | +return0; |
| 55 | + } |
| 56 | +if (memo[prevIndex +1][currIndex] >=0) { |
| 57 | +//because we initialize all elements in memo to be -1, |
| 58 | +// so if it's not -1, then it means we have computed this value before, |
| 59 | +// we'll just return it and this way it avoid duplicate recursion |
| 60 | +returnmemo[prevIndex +1][currIndex]; |
| 61 | + } |
| 62 | +inttaken =0; |
| 63 | +if (prevIndex <0 ||nums[currIndex] >nums[prevIndex]) { |
| 64 | +taken =1 +recusionWithMemo(nums,currIndex,currIndex +1,memo); |
| 65 | + } |
| 66 | +intnotTaken =recusionWithMemo(nums,prevIndex,currIndex +1,memo); |
| 67 | +memo[prevIndex +1][currIndex] =Math.max(taken,notTaken); |
| 68 | +returnmemo[prevIndex +1][currIndex]; |
| 69 | + } |
| 70 | + } |
| 71 | + |
| 72 | +publicstaticclassSolution3 { |
| 73 | +/** |
| 74 | + * DP solution |
| 75 | + * Time: O(n^2) |
| 76 | + * Space: O(n) |
| 77 | + */ |
| 78 | +publicintlengthOfLIS(int[]nums) { |
| 79 | +if (nums.length ==0) { |
| 80 | +return0; |
| 81 | + } |
| 82 | +int[]dp =newint[nums.length]; |
| 83 | +dp[0] =1; |
| 84 | +intresult =1; |
| 85 | +for (inti =1;i <nums.length;i++) { |
| 86 | +intmaxVal =0; |
| 87 | +for (intj =0;j <i;j++) { |
| 88 | +if (nums[i] >nums[j]) { |
| 89 | +maxVal =Math.max(maxVal,dp[j]); |
| 90 | + } |
| 91 | + } |
| 92 | +dp[i] =maxVal +1; |
| 93 | +result =Math.max(result,dp[i]); |
| 94 | + } |
| 95 | +returnresult; |
| 96 | + } |
| 97 | + } |
8 | 98 |
|
| 99 | +publicstaticclassSolution4 { |
9 | 100 | /** |
10 | | - * credit: https://discuss.leetcode.com/topic/28719/short-java-solution-using-dp-o-n-log-n |
11 | | - * The idea is that as you iterate the sequence, |
12 | | - * you keep track of the minimum value a subsequence of given length might end with, |
13 | | - * for all so far possible subsequence lengths. |
14 | | - * So dp[i] is the minimum value a subsequence of length i+1 might end with. |
15 | | - * Having this info, for each new number we iterate to, |
16 | | - * we can determine the longest subsequence where it can be appended using binary search. |
17 | | - * The final answer is the length of the longest subsequence we found so far. |
| 101 | + * use binary search. |
| 102 | + * Time: O(nlogn) |
| 103 | + * Space: O(n) |
| 104 | + * <p> |
| 105 | + * The reason we can use binary search here is because all numbers we put into dp array are sorted |
18 | 106 | */ |
19 | 107 | publicintlengthOfLIS(int[]nums) { |
20 | 108 | int[]dp =newint[nums.length]; |
21 | 109 | intlen =0; |
22 | | -for (intx :nums) { |
23 | | -/**Java Doc of this binarySearch API: |
24 | | - * @return index of the search key, if it is contained in the array |
25 | | - * within the specified range; |
26 | | - * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The |
27 | | - * <i>insertion point</i> is defined as the point at which the |
28 | | - * key would be inserted into the array: the index of the first |
29 | | - * element in the range greater than the key, |
30 | | - * or <tt>toIndex</tt> if all |
31 | | - * elements in the range are less than the specified key. Note |
32 | | - * that this guarantees that the return value will be >= 0 if |
33 | | - * and only if the key is found.*/ |
34 | | -intindex =Arrays.binarySearch(dp,0,len,x); |
| 110 | +for (intnum :nums) { |
| 111 | +intindex =Arrays.binarySearch(dp,0,len,num); |
35 | 112 | if (index <0) { |
36 | 113 | index = -(index +1); |
37 | 114 | } |
38 | | -dp[index] =x; |
| 115 | +dp[index] =num; |
39 | 116 | if (index ==len) { |
40 | 117 | len++; |
41 | 118 | } |
|