package leetcode;

import java.util.HashMap;
import java.util.Map;

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

    private int lengthOfLIS(int[] nums, int idx, Map<Integer, Integer> memo) {
        if (memo.containsKey(idx)) {
            return memo.get(idx);
        }
        int maxLength = 0;
        for (int i = idx; i < nums.length; i++) {
            if (nums[idx] < nums[i]) {
                int length = lengthOfLIS(nums, i, memo) + 1;
                maxLength = Math.max(maxLength, length);
            }
        }
        memo.put(idx, maxLength);
        return maxLength;
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -159,38 +159,32 @@
 %0A        int max
-Length
  = 0;%0A        Ma
@@ -181,37 +181,25 @@
         
-Map%3C
 Integer
-, Integer%3E
+%5B%5D
  memo = 
@@ -206,19 +206,28 @@
 new 
-HashMap%3C%3E()
+Integer%5Bnums.length%5D
 ;%0A  
@@ -280,36 +280,43 @@
             
-int length =
+max = Math.max(max,
  lengthOfLIS
@@ -338,60 +338,8 @@
  + 1
-;%0A            maxLength = Math.max(maxLength, length
 );%0A 
@@ -357,38 +357,32 @@
       return max
-Length
 ;%0A    %7D%0A%0A    pri
@@ -386,16 +386,23 @@
 private 
+static 
 int leng
@@ -434,29 +434,17 @@
 dx, 
-Map%3C
 Integer
-, Integer%3E
+%5B%5D
  mem
@@ -468,25 +468,21 @@
 memo
-.containsKey(idx)
+%5Bidx%5D != null
 ) %7B%0A
@@ -508,17 +508,13 @@
 memo
-.get(idx)
+%5Bidx%5D
 ;%0A  
@@ -536,22 +536,16 @@
  int max
-Length
  = 0;%0A  
@@ -651,20 +651,27 @@
     
-int length =
+max = Math.max(max,
  len
@@ -697,16 +697,17 @@
 emo) + 1
+)
 ;%0A      
@@ -716,136 +716,673 @@
     
+%7D%0A
     
-maxLength = Math.max(maxLength, length);%0A            %7D%0A        %7D%0A        memo.put(idx, maxLength);%0A        return maxLength;
+    %7D%0A        memo%5Bidx%5D = max;%0A        return max;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem300 prob = new Problem300();%0A        System.out.println(prob.lengthOfLIS(new int%5B%5D%7B4, 10, 4, 3, 8, 9%7D)); // 3%0A        System.out.println(prob.lengthOfLIS(new int%5B%5D%7B3, 5, 2, 4%7D)); // 2%0A        System.out.println(prob.lengthOfLIS(new int%5B%5D%7B1%7D)); // 1%0A        System.out.println(prob.lengthOfLIS(new int%5B%5D%7B1, 2%7D)); // 2%0A        System.out.println(prob.lengthOfLIS(new int%5B%5D%7B1, 2, 3%7D)); // 3%0A        System.out.println(prob.lengthOfLIS(new int%5B%5D%7B%7D)); // 0%0A        System.out.println(prob.lengthOfLIS(new int%5B%5D%7B10, 9, 2, 5, 3, 7, 101, 18%7D)); // 4
 %0A   

Update problem 300