package leetcode;

/**
 * https://leetcode.com/problems/longest-increasing-subsequence/
 */
public class Problem300 {
    public int lengthOfLIS(int[] nums) {
        int max = 0;
        Integer[] memo = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, lengthOfLIS(nums, i, memo) + 1);
        }
        return max;
    }

    private static int lengthOfLIS(int[] nums, int idx, Integer[] memo) {
        if (memo[idx] != null) {
            return memo[idx];
        }
        int max = 0;
        for (int i = idx; i < nums.length; i++) {
            if (nums[idx] < nums[i]) {
                max = Math.max(max, lengthOfLIS(nums, i, memo) + 1);
            }
        }
        memo[idx] = max;
        return max;
    }
}

@@ -157,36 +157,589 @@
  %7B%0A        i
-nt max = 0;%0A
+f (nums.length == 0) %7B%0A            return 0;%0A        %7D%0A        int max = 0;%0A        int%5B%5D memo = new int%5Bnums.length%5D;%0A        for (int i = nums.length - 1; i %3E= 0; i--) %7B%0A            int tmpMax = 0;%0A            for (int j = i; j %3C nums.length; j++) %7B%0A                if (nums%5Bi%5D %3C nums%5Bj%5D) %7B%0A                    tmpMax = Math.max(tmpMax, memo%5Bj%5D + 1);%0A                %7D%0A            %7D%0A            memo%5Bi%5D = tmpMax;%0A            max = Math.max(max, tmpMax);%0A        %7D%0A        return max + 1;%0A    %7D%0A%0A//    public int lengthOfLIS(int%5B%5D nums) %7B%0A//        int max = 0;%0A//
         Inte
@@ -769,32 +769,34 @@
 r%5Bnums.length%5D;%0A
+//
         for (int
@@ -819,32 +819,34 @@
 .length; i++) %7B%0A
+//
             max 
@@ -886,32 +886,34 @@
  i, memo) + 1);%0A
+//
         %7D%0A      
@@ -898,32 +898,34 @@
 1);%0A//        %7D%0A
+//
         return m
@@ -928,23 +928,29 @@
 rn max;%0A
+//
     %7D%0A
-%0A
+//%0A//
     priv
@@ -1011,24 +1011,26 @@
 r%5B%5D memo) %7B%0A
+//
         if (
@@ -1046,24 +1046,26 @@
  != null) %7B%0A
+//
             
@@ -1082,16 +1082,18 @@
 o%5Bidx%5D;%0A
+//
         
@@ -1086,32 +1086,34 @@
 x%5D;%0A//        %7D%0A
+//
         int max 
@@ -1109,32 +1109,34 @@
    int max = 0;%0A
+//
         for (int
@@ -1165,24 +1165,26 @@
 gth; i++) %7B%0A
+//
             
@@ -1206,24 +1206,26 @@
  nums%5Bi%5D) %7B%0A
+//
             
@@ -1277,24 +1277,26 @@
 memo) + 1);%0A
+//
             
@@ -1289,32 +1289,34 @@
 //            %7D%0A
+//
         %7D%0A      
@@ -1301,32 +1301,34 @@
   %7D%0A//        %7D%0A
+//
         memo%5Bidx
@@ -1332,24 +1332,26 @@
 idx%5D = max;%0A
+//
         retu
@@ -1354,20 +1354,22 @@
 return max;%0A
+//
     %7D%0A%7D%0A

Update problem 300