300. Longest Increasing Subsequence

// DP Solution:
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int max = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        
        max = Math.max(max, dp[i]);
    }
    
    return max;
}

// Binary Search:
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int len = 0;
    for (int num : nums) {
        int index = Arrays.binarySearch(dp, 0, len, num);
        if (index < 0) {
            index = -(index + 1);
        }

        dp[index] = num;
        if (index == len) {
            len++;
        }
    }

    return len;
}