Longest Increasing Subsequence - Two DP solutions

Array     Binary Search     C++     Dynamic Programming     Medium    

Problem Statement:

Given an integer array nums, return the length of the longest strictly increasing subsequence.

 

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

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

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

 

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

 

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Solution:

Fastest O(N log N) solution in C++:

 
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> sub;
        for (int n: nums)
        {
            if (sub.size()==0 || n > sub[sub.size()-1])
                sub.push_back(n);
            else
            {
                vector<int>::iterator it = lower_bound(sub.begin(),sub.end(),n);
                *it = n;
            }
        }
        return sub.size();
    }
};
 

O(N^2) solution: C++:

 
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,1);
        for(int i=0;i<n;i++) for(int j=0;j<i;j++) if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1); 
        return *max_element(dp.begin(), dp.end());
    }
};
 

Python:

 
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1 for _ in range(n)]
        for i in range(n):
            for j in range(i):
                if nums[i]>nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)
 

Java:

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

JavaScript:

 
var lengthOfLIS = function(nums) {
    var n = nums.length;
    var dp = Array(n);
    dp.fill(1);
    for(let i=0; i<n; 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);
};