300. Longest Increasing Subsequence

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        return helper(nums, Integer.MIN_VALUE, 0);
        
    }
    
    public int helper(int[] nums, int before, int index) {
        if (index == nums.length) {
            return 0;
        }
        
        int num = 0;
        
        if (nums[index] > before) {
            num = 1 + helper(nums, nums[index], index + 1);
        }
        
        int num2 = helper(nums, before, index + 1);
        
        return Math.max(num, num2);
    }
}

Backtracking을 쓴다고 생각했는데 아닌듯..
Time limit exceeded

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int m = 1;
        
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    maxval = Math.max(maxval, dp[j]);
                }
            }
            dp[i] = maxval + 1;
            m = Math.max(m, dp[i]);
        }
        return m;
    }
}

Dynamic programming 을 쓴 n^2 solution

Runtime: 87 ms, faster than 12.88% of Java online submissions for Longest Increasing Subsequence.
Memory Usage: 41.1 MB, less than 12.60% of Java online submissions for Longest Increasing Subsequence.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}

다들 천재라고 하는 nlogn solution
전씨와 함께 탐구하고 싶네요^^

Runtime: 2 ms, faster than 96.54% of Java online submissions for Longest Increasing Subsequence.
Memory Usage: 41.2 MB, less than 12.02% of Java online submissions for Longest Increasing Subsequence.