Start learning free

LESSON 457 OF 540 · DYNAMIC PROGRAMMING

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

Practice O(n2) Read the full explanation

You are given an array 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 11
    Ctrl + Enter to check

    GO · DYNAMIC PROGRAMMING

    Longest Increasing Subsequence in Go, explained

    Problem overview

    The function lengthOfLIS receives a slice of integers, nums, and returns the length of its longest strictly increasing subsequence. A subsequence is what remains after deleting some elements, possibly none, without reordering the rest. "Strictly increasing" means every element is larger than the one before it, so two equal values can never both be in it. Only the length is returned, not the subsequence itself.

    For nums = [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4. One such subsequence is [2, 3, 7, 101], another is [2, 5, 7, 18], and none has five elements. For [0, 1, 0, 3, 2, 3] the answer is 4 ([0, 1, 2, 3]), and for [7, 7, 7, 7, 7, 7, 7] it is 1, because equal values don't increase.

    The lesson asks for O(n²) time and O(n) extra space, where n is len(nums).

    Approach: the best subsequence ending at each index

    Trying every subsequence is out of reach: a slice of 2500 elements has 2 to the power 2500 of them. Instead, solve smaller versions of the problem and reuse their answers.

    Let dp[i] be the length of the longest strictly increasing subsequence that ends with nums[i]. Fixing the last element is what makes the pieces fit together:

    • Every dp[i] is at least 1, because nums[i] alone is such a subsequence.
    • For every earlier index j < i with nums[j] < nums[i], the element nums[i] can be placed after the best subsequence that ends at j. That gives length dp[j] + 1.
    • So dp[i] is 1 plus the largest dp[j] among those j, or just 1 when no earlier element is smaller.

    The longest subsequence of the whole slice can end anywhere, so the answer is the largest dp[i], not the last one.

    A faster O(n log n) method exists. It keeps, for each length, the smallest value an increasing subsequence of that length can end with, and places each element in that list with a binary search. This lesson practises the table version.

    Step by step

    1. Store the length in n. Both loops run over the indexes of nums.
    2. Create dp with make([]int, n). A new slice of ints is full of zeros, so the starting values must be set.
    3. Loop over dp with for i := range dp. With one variable, range gives the indexes.
    4. Set every dp[i] to 1. A single element is an increasing subsequence of length 1, so no entry is ever below 1.
    5. Create best, starting at 0. It holds the longest length found so far.
    6. Loop over i from 0 to n - 1. Each dp[i] needs only entries to its left, which are final by the time the loop gets to i.
    7. Loop over every earlier index j from 0 up to i - 1. For i = 0 there are none, and the loop doesn't run.
    8. Test nums[j] < nums[i]. It must be < and not <=, because an equal value can't follow.
    9. Update dp[i] with max(dp[i], dp[j]+1). Keeping the largest value over all valid j gives the answer for i.
    10. Update best with max(best, dp[i]), after the inner loop and still inside the outer one. At that point dp[i] has seen every j.
    11. Return best once the outer loop is done.

    The solution in Go

    func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    best := 0
    for i := 0; i < n; i++ {
        for 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 Go details worth a closer look:

    • The built-in max. Since Go 1.21, max and min are built into the language and take two or more values of the same ordered type. Older versions needed a hand-written helper; Go 1.22 does not.
    • for i := range dp loops over the indexes, 0 to len(dp) - 1. The value is not needed here, so only i is named.
    • Zero values. make([]int, n) gives zeros, which is why the first loop sets everything to 1 before any comparison reads the table.
    • Two ways to write a counted loop. The first loop uses range because it only needs every index. The nested loops use the three-part for because the inner bound, j < i, depends on the outer variable.

    Complexity

    Time: O(n²). The two loops look at each pair j < i once, which is n · (n - 1) / 2 pairs. With n up to 2500 that is about 3 million comparisons.

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

    Edge cases and common mistakes

    • Using <=. It counts equal values as increasing. On [7, 7, 7, 7, 7, 7, 7] that version returns 7 instead of 1.
    • Returning dp[n-1]. That is the best subsequence ending at the last element, not the best overall. On [1, 2, 3, 0] the last entry is 1, while the answer is 3. Keeping best avoids the problem.
    • Starting dp at 0. Then an element with no smaller element before it would count as a subsequence of length 0, and a one-element slice would return 0.
    • Confusing a subsequence with a substring. The chosen elements don't have to be next to each other. In [0, 1, 0, 3, 2, 3] the answer uses indexes 0, 1, 4 and 5.
    • Descending input. No pair satisfies nums[j] < nums[i], so every entry stays 1 and the answer is 1.

    Testing

    Printing nums and then dp for [10, 9, 2, 5, 3, 7, 101, 18] gives:

    [10 9 2 5 3 7 101 18] [1 1 1 2 2 3 4 4]

    Each value in the second list is the best length ending at the number in the same position of the first. For example, dp[5] is 3 for nums[5] = 7: the subsequence [2, 5, 7] or [2, 3, 7] ends there.

    The largest entry is 4. For [0, 1, 0, 3, 2, 3] the table is [1 2 1 3 3 4], and again the answer is the largest entry. More inputs to try:

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