@@ -19,47 +19,53 @@ Your algorithm should run in O(n2) complexity.
1919Credits:
2020Special thanks to @pbrother for adding this problem and creating all test cases.*/
2121public class LengthIncreasingSubsequence {
22+ public static void main (String ...strings ){
23+ LengthIncreasingSubsequence test =new LengthIncreasingSubsequence ();
24+ int []nums =new int []{10 ,9 ,2 ,5 ,3 ,7 ,101 ,18 };
25+ // int[] nums = new int[]{10,9,2,5,3,4};
26+ // int[] nums = new int[]{1,3,6,7,9,4,10,5,6};
27+ // int[] nums = new int[]{18,55,66,2,3,54};
28+ System .out .println (test .lengthOfLIS (nums ));
29+ }
30+
31+ /**This is the closest I got, passed all normal cases, made it to 22/23 test cases, but got TLE, as I expected,
32+ * since this algorithm runs in O(n^3) time.
33+ * My idea: compute a 2D tabular: n*n.
34+ *
35+ * Then miracle happens, I was about to turn to Discuss, before that, I clicked the Show Tags button, it says:
36+ * Binary Search, this hints me to take a second look at my code, then I added this line:
37+ * if(nums.length-i < max) return max;
38+ * then it got AC'ed!
39+ * This is the power of pruning! So Cool!
40+ *
41+ * Also, another key was that let j start from i, not 0, we don't need to initialize the bottom left part to 1, just
42+ * leave them as zero, that's fine, since we don't need to touch that part at all!
43+ * This also saves time! Cool!
44+ * */
2245public int lengthOfLIS (int []nums ) {
23- if (nums ==null ||nums .length ==0 )return 0 ;
24-
46+
47+ if (nums ==null ||nums .length ==0 )
48+ return 0 ;
49+
2550int [][]dp =new int [nums .length ][nums .length ];
2651int max =0 ;
27- for (int i =0 ;i <nums .length ;i ++){
28- int currentMaxForThisRow =nums [i ];
29- for (int j =0 ;j <nums .length ;j ++){
30- if (j <=i )dp [i ][j ] =1 ;
31- else {
32- if (nums [j ] >nums [i ]) {
33- if (nums [j ] >currentMaxForThisRow ) {
34- dp [i ][j ] =dp [i ][j -1 ]+1 ;
35- currentMaxForThisRow =nums [j ];
36- }else {
37- dp [i ][j ] =dp [i ][j -1 ];
38- //in this case, we need to figure out when should we update currentMaxForThisRow?
39- for (int k =j -1 ;k >=0 ;k --){
40- if (nums [k ] <nums [j ]){
41- if (dp [i ][k ]+1 ==dp [i ][j ] &&nums [j -1 ] >nums [j ]){
42- currentMaxForThisRow =nums [j ];
43- }
44- break ;
45- }
46- }
52+ for (int i =0 ;i <nums .length ;i ++) {
53+ if (nums .length -i <max )return max ;
54+ for (int j =i ;j <nums .length ;j ++) {
55+ if (nums [j ] >nums [i ]) {
56+ for (int k =j -1 ;k >=i ;k --) {
57+ if (nums [k ] <nums [j ]) {
58+ dp [i ][j ] =Math .max (dp [i ][k ] +1 ,dp [i ][j ]);
4759 }
4860 }
49- else dp [ i ][ j ] = dp [ i ][ j - 1 ];
50- }
61+ } else
62+ dp [ i ][ j ] = 1 ;
5163max =Math .max (max ,dp [i ][j ]);
5264 }
5365 }
5466CommonUtils .printMatrix (dp );
5567return max ;
68+
5669 }
5770
58- public static void main (String ...strings ){
59- LengthIncreasingSubsequence test =new LengthIncreasingSubsequence ();
60- // int[] nums = new int[]{10, 9, 2, 5, 3, 7, 101, 18};
61- // int[] nums = new int[]{10,9,2,5,3,4};
62- int []nums =new int []{1 ,3 ,6 ,7 ,9 ,4 ,10 ,5 ,6 };
63- System .out .println (test .lengthOfLIS (nums ));
64- }
6571}