Leetcode 300 "Longuest Increasing Subsequence"

November 23, 2021

Title

(300. Subsequence)[https://leetcode.com/problems/longest-increasing-subsequence/]

Result

Runtime: 196 ms, faster than 5.02% of Java online submissions for Longest Increasing Subsequence.

Memory Usage: 41.9 MB, less than 6.22% of Java online submissions for Longest Increasing Subsequence.

class Solution {
    int total = Integer.MIN_VALUE;
    int thisTotal = Integer.MIN_VALUE;
    Integer[] cache;
    
    public int lengthOfLIS(int[] nums) {
        cache = new Integer[nums.length+1];
        return lengthOfLISAux(0, nums, Integer.MIN_VALUE);
    }
    
    public int lengthOfLISAux(int index, int[] nums, int currMax) {
        if(index >= nums.length)
            return 0;
        
        int red = Integer.MIN_VALUE;
        if(currMax < nums[index]) {
            if(cache[index] == null)
                cache[index] = 1 + lengthOfLISAux(index+1, nums, nums[index]);
            red = cache[index];
        }
        int green = lengthOfLISAux(index+1, nums, currMax);
        
        return Math.max(red, green);
    }
}