Longest Increasing Subsequence

Medium

Python

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

Java

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

Key Insight

[1]*n vs Arrays.fill(). Python max(dp) vs Java explicit loop.

Python → Java Differences

[1]*n vs Arrays.fill(dp,1)
max(dp) vs manual max
O(n^2) DP identical

Python

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

Java

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

Algorithm Steps

1. dp[i] = LIS ending at i
2. Check all j<i
3. Return max

← Previous All Dynamic Programming Next →