Leetcode — 300.Longest Increasing Subsequence

1. Problem

Given an integer array nums, return the length of the longest strictly increasin g 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

2. Initial solution

In the previous dp solution for ‘Longest common subsequence’, I got an idea for this solution.

1. Sort given ‘nums’ array.
2. Set initial previous value as the lowest value from constraints.
3. Using dp approach, find longest common subsequence
4. But if the value of current row is same with previous one, just copy the value from last row without any operations.

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int dp[2501][2501] = {0};
        vector<int> nums2 = nums;
        sort(nums2.begin(), nums2.end());

        int prev = pow(-10, 4);
        for(int i = 0; i < nums2.size(); i++) {
            for(int j = 0; j < nums.size(); j++) {
                if(nums2[i] == prev) {
                    dp[i+1][j] = dp[i][j];
                    if(j == nums.size()-1) 
                    {
                        dp[i+1][j+1] = dp[i][j+1]; 
                    }
                }
                else {
                    dp[i+1][j+1] = (nums2[i] == nums[j]) ? dp[i][j] + 1 : max(dp[i+1][j], dp[i][j+1]);
                }
            }
            prev = nums2[i];
        }
        
        return dp[nums2.size()][nums.size()];
    }
};

Graphical description of the solution

Result of this algorithm

3. Let’s optimize

By using dp, i can solve this problem. But this is not the best solution.

1. One-Dimensional DP

class Solution { 
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1); // create a vector with same size of nums.
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                if (nums[i] > nums[j] && dp[i] < dp[j] + 1)
//if current value is bigger than nums[i] and if dp[i] is smaller than dp[j]+1
                    dp[i] = dp[j] + 1;
        return *max_element(dp.begin(), dp.end());
    }
};

2. Greedy & binary search

Let’s assume that we have an array like [2, 6, 8, 9, 3, 4]

Instead of creating a new sub array whenever there comes up lower value than the last element of current sub array, we can just keep it into same array.

1. 2 -> 6 -> 8 -> 9, there is no problem til 9.
2. Oops! 3 comes up, Let’s find the secondary smallest value in the array with bin search and replace it with 3
3. Now we got [2,3,8,9]. Although we changed 6 to 3, there is no problem in the whole count at all. First, if there are more values which is smaller than 8 and 9, It will longer than [2,6,8,9] eventually. Second, even if there is no values anymore, we can keep the length 4. The value inside array doesn’t matter.

int lengthOfLIS(vector<int>& nums) {
  vector<int> sub;
  sub.push_back(nums[0]);

  for(int i=1; i < nums.size(); i++)
  {
    if(nums[i] > sub.back()) { 
      sub.push_back(nums[i]);
    }    
    else {
//Bin search by using STL
      auto it = lower_bound(sub.begin(), sub.end(), nums[i]);
      *it = nums[i];
    } 
  }

  return sub.size();
}

Reference

• problem source : https://leetcode.com/problems/longest-increasing-subsequence/description/
• Greedy approach and 1-D DP : https://leetcode.com/problems/longest-increasing-subsequence/solutions/1326308/c-python-dp-binary-search-bit-segment-tree-solutions-picture-explain-o-nlogn/?orderBy=most_votes