300. Longest Increasing Subsequence • Algorithm Solutions

1. Description

Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

2. Example

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

3. Constraints

1 <= nums.length <= 2500
$-10^4$ <= nums[i] <= $10^4$

4. Follow up

Could you come up with the O($n^2$) solution?
Could you improve it to O(nlogn) time complexity?

5. Solutions

My Accepted Solution

n = i_nums.size()
Time complexity: O($n^2$)
Space complexity: O(n)

class Solution 
{
public:
    // int lengthOfLIS(vector<int>& nums)
    int lengthOfLIS(const vector<int> &i_nums) 
    {
        if(i_nums.empty()) return 0;
        
        vector<int> longestSubsequenceLength(i_nums.size(), 1);
        for(int i = 1; i < i_nums.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(i_nums[i] > i_nums[j])
                {
                    longestSubsequenceLength[i] = max(longestSubsequenceLength[j] + 1, longestSubsequenceLength[i]);
                }
            }
        }
        
        // longestSubsequenceLength[i] means the longest length of subsequence ending at the index i
        // while the result may not end at the last index
        // so we could not treat longestSubsequenceLength.back() as the result as other dp questions
        return *max_element(longestSubsequenceLength.begin(), longestSubsequenceLength.end());
    }
};

5.1 Dynamic Programming && Binary Search

n = i_nums.size()
Time complexity: O(nlogn)
Space complexity: O(n)

// use the thought of greedy: if we want to get a longer subsequence, we hope its last value is very small
// so, we could have more chances to append more values
// we use minLastValueOfLength to represent min values of the given lenth subsequence's last value
class Solution 
{
public:
    // int lengthOfLIS(vector<int>& nums)
    int lengthOfLIS(const vector<int> &i_nums) 
    {
        if(i_nums.empty()) return 0;
        
        int longestLength = 1;
        vector<int> minLastValueOfLength(i_nums.size() + 1); 
        minLastValueOfLength[longestLength] = i_nums.front();
        for(int i = 1; i < i_nums.size(); i++)
        {
            if(i_nums[i] > minLastValueOfLength[longestLength])
            {
                // in this case, we could append a new value to the longest subsequence, so the longest lenght could increase one
                longestLength++;
                minLastValueOfLength[longestLength] = i_nums[i];
            }
            else
            {
                // if we can't append a new value to the longest subsequence directlly
                // we try to make a shorter subseqence's last value more little
                // so we may have chances to use it later to create a longer sequence
                auto iter = lower_bound(minLastValueOfLength.begin() + 1, minLastValueOfLength.begin() + longestLength + 1, i_nums[i]);
                if(iter == minLastValueOfLength.begin() + longestLength + 1)
                    minLastValueOfLength[1] = i_nums[i];
                else
                    *iter = i_nums[i];
            }
        }

        return longestLength;
    }
};