Longest Increasing Subsequence

Problem Statement

Given an array of numbers, find the length of the longest subsequence that’s strictly increasing. This medium-level DP challenge is like climbing a numerical ladder—how high can you go?

Example

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]

Output: 4 (2, 3, 7, 101)

Input: nums = [0, 1, 0, 3, 2, 3]

Output: 4 (0, 1, 2, 3)

Input: nums = [7, 7, 7]

Output: 1 (no increase possible)

Code

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

def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# Example usage
print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
print(length_of_lis([0, 1, 0, 3, 2, 3]))  # 4
            

function lengthOfLIS(nums) {
    if (!nums.length) return 0;
    let dp = new Array(nums.length).fill(1);
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp);
}

// Example usage
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));  // 4
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]));  // 4- 
            

Explanation

• DP Insight: dp[i] = longest increasing subsequence ending at i.
• Steps: For each num, check all prior nums; extend if greater.
• Flow Example ([2,5,3,7]): dp[0]=1, dp[1]=2 (2,5), dp[2]=2 (2,3), dp[3]=3 (2,3,7).
• Why It Works: Builds all possible increasing sequences.

Note