Start learning free

LESSON 452 OF 535 · DYNAMIC PROGRAMMING

Longest Increasing Subsequence in C++: O(n²) Dynamic Programming

Practice O(n2) Read the full explanation

You are given a vector of integers nums. Return the length of its longest strictly increasing subsequence.

A subsequence is what remains after deleting some elements, possibly none, without changing the order of the others. For example, [3, 6, 2, 7] is a subsequence of [0, 3, 1, 6, 2, 2, 7]. It is strictly increasing when every element is larger than the one before it, so two equal values can't both be in it.

 

Example 1:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: [2, 3, 7, 101] is strictly increasing, and so are [2, 5, 7, 18] and a few others of length 4.
None has 5 elements. Only the length is returned.

Example 2:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: [0, 1, 2, 3] uses the first 0, the 1, the 2 and the last 3.

Example 3:

Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1
Explanation: Equal values don't increase, so the longest strictly increasing subsequence is a single 7.

 

Constraints:

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

Note:

Your algorithm should run in O(n2) time and use O(n) extra space, where n is the length of nums.

A faster O(n log n) method exists: keep, for each length, the smallest value that an increasing subsequence of that length can end with, and place every element in that list with a binary search.



Trying every subsequence is far too slow: 2500 elements have 22500 subsequences. Solve smaller versions of the problem instead: let dp[i] be the length of the longest strictly increasing subsequence that ends with nums[i]. Every dp[i] is at least 1: the element alone is such a subsequence.

Fill dp from left to right. For every earlier index j < i with nums[j] < nums[i], the element nums[i] can be added to the end of the best subsequence that ends at j, which gives the length dp[j] + 1. So dp[i] is 1 plus the largest such dp[j], or just 1 when no earlier element is smaller.
The longest subsequence can end anywhere, so the answer is the largest dp[i], not necessarily the last one.

Every pair j < i is looked at once, and there are n · (n - 1) / 2 pairs: O(n2) time. The table takes O(n) space.
STEP 1 OF 9
    Ctrl + Enter to check

    C++ · DYNAMIC PROGRAMMING

    Longest Increasing Subsequence in C++, explained

    Problem overview

    The function lengthOfLIS receives a vector<int> called nums and returns the length of its longest strictly increasing subsequence. A subsequence keeps some elements in their original order and drops the rest, so [3, 6, 2, 7] is a subsequence of [0, 3, 1, 6, 2, 2, 7]. It is strictly increasing when every element is larger than the one before it, so two equal values can't both be in it. Only the length is returned, not the subsequence.

    For [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4: [2, 3, 7, 101] and [2, 5, 7, 18] both work, and no subsequence has 5 elements. For [0, 1, 0, 3, 2, 3] it is 4 ([0, 1, 2, 3]), and for seven 7s it is 1, because equal values don't increase.

    The lesson asks for O(n²) time and O(n) extra space.

    Approach: the best subsequence ending at each element

    Checking every subsequence is hopeless: 2500 elements have 2 to the power 2500 of them. Instead, solve a smaller question for each position. Let dp[i] be the length of the longest strictly increasing subsequence that ends with nums[i]. Every dp[i] is at least 1, since the element alone is such a subsequence.

    To compute dp[i], look at every earlier index j < i. When nums[j] < nums[i], the element nums[i] can be added after the best subsequence that ends at j, which gives length dp[j] + 1. Keep the largest such value. If no earlier element is smaller, dp[i] stays 1.

    The longest subsequence can end anywhere, so the answer is the largest dp[i], not necessarily the last one. For [10, 9, 2, 5, 3, 7, 101, 18] the table is 1 1 1 2 2 3 4 4. The entry for 7 is 3 (through 2, 3, 7 or 2, 5, 7), the entry for 101 is 4, and 18 also reaches 4. For [0, 1, 0, 3, 2, 3] the table is 1 2 1 3 3 4.

    The statement also mentions an O(n log n) method that keeps, for each length, the smallest value an increasing subsequence of that length can end with, and places every element in that list with a binary search. This lesson builds the simpler table.

    A small example shows how the entries build on each other. For [1, 3, 2, 4, 3] the table is 1 2 2 3 3. The 3 at index 1 extends the 1. The 2 at index 2 also extends only the 1, so it gets 2, not 3, because 3 is not smaller than 2. The 4 at index 3 can follow either the 3 or the 2, both with length 2, so it gets 3. The last 3 follows the 2 (through 1, 2, 3), which also gives 3, and the answer is the largest entry, 3.

    Step by step

    1. Store the length. Put nums.size() in an int named n. Both loops run over the indexes of nums.
    2. Create the table. A vector<int> named dp of size n, every entry 1, because each element is a subsequence of length 1 by itself.
    3. Create best, an int starting at 0, for the longest length seen so far.
    4. Loop over i from 0 up to n - 1. Each entry needs only the entries before it, which are finished by then.
    5. Loop over every earlier index j from 0 up to i - 1. For i = 0 it doesn't run.
    6. Test nums[j] < nums[i]. The comparison is strict, because an equal value can't follow.
    7. Update dp[i] to the larger of dp[i] and dp[j] + 1.
    8. Update best after the inner loop, when dp[i] is final.
    9. Return best after the outer loop.

    The solution in C++

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

    The C++ details worth a closer look:

    • vector<int> dp(n, 1). The constructor takes the size first and the value of every element second. Writing dp(n) alone would fill the vector with zeros instead.
    • int n = nums.size(). size() is unsigned, and the conversion to int is safe here because the length is at most 2500. Keeping n as an int keeps the loop counters and the comparisons i < n and j < i between ints.
    • max with two ints. max(dp[i], dp[j] + 1) compiles because both arguments are int. Mixing types, such as an int and a size_t, makes the template deduction fail.
    • The input is passed by reference. vector<int>& nums avoids copying up to 2500 numbers. The function only reads it.

    Complexity

    Time: O(n²). Every pair j < i is examined once, and there are n · (n - 1) / 2 pairs. Each examination is a comparison and possibly a max.

    Space: O(n). The table dp has one entry per element, and the other variables are single integers.

    Edge cases and common mistakes

    • One element. [5] gives 1: the inner loop never runs, and best becomes dp[0], which is 1.
    • All equal values. Seven 7s give 1, because the strict comparison never fires.
    • Decreasing input. [5, 4, 3, 2, 1] gives 1, and an increasing input such as [1, 2, 3, 4] gives 4, with the table 1 2 3 4.
    • Using <=. That would count equal values as increasing and return 7 for seven 7s.
    • Returning dp[n - 1]. The best subsequence may end earlier. In [0, 1, 0, 3, 2, 3] the answer 4 happens to be at the end, but in [1, 2, 3, 0] the last entry is 1 while the answer is 3.
    • Starting dp at 0. Every element is a subsequence of its own, so the entries start at 1. With zeros the result would be one too small.
    • Confusing subsequence with substring. The chosen elements don't have to be neighbours: in the first example 2, 3, 7 and 101 are spread across the vector.

    Testing

    • [10, 9, 2, 5, 3, 7, 101, 18] gives 4.
    • [0, 1, 0, 3, 2, 3] gives 4.
    • [7, 7, 7, 7, 7, 7, 7] gives 1.
    • [5] gives 1.
    • [5, 4, 3, 2, 1] gives 1.
    • [1, 2, 3, 4] gives 4.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free