Start learning free

LESSON 457 OF 540 · DYNAMIC PROGRAMMING

Longest Increasing Subsequence in Scala: 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 9
    Ctrl + Enter to check

    SCALA · DYNAMIC PROGRAMMING

    Longest Increasing Subsequence in Scala, explained

    Problem overview

    The method lengthOfLIS(nums: Array[Int]): Int returns the length of the longest strictly increasing subsequence of nums. A subsequence is what remains after deleting some elements, possibly none, without changing the order of the rest. It is strictly increasing when 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 = Array(10, 9, 2, 5, 3, 7, 101, 18) the answer is 4. The subsequence [2, 3, 7, 101] works, and so does [2, 5, 7, 18]. No increasing subsequence has 5 elements. For Array(0, 1, 0, 3, 2, 3) the answer is also 4, from [0, 1, 2, 3]. For seven 7s the answer is 1, because equal values do not increase.

    Approach: the best subsequence that ends at each index

    Trying every subsequence is hopeless: 2500 elements have 2^2500 of them. The lesson instead solves a smaller question for each index. Let dp(i) be the length of the longest strictly increasing subsequence that ends with nums(i). Every dp(i) is at least 1, because the element alone is such a subsequence.

    The table is filled 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 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.

    For Array(10, 9, 2, 5, 3, 7, 101, 18) the table is:

    1 1 1 2 2 3 4 4

    The 5 at index 3 extends the subsequence ending in 2, so its entry is 2. The 7 at index 5 extends either the 5 or the 3, both with length 2, so its entry is 3. The 101 gives 4, and so does the 18. For Array(0, 1, 0, 3, 2, 3) the table is 1 2 1 3 3 4, and the maximum is again 4.

    The statement mentions a faster O(n log n) method. It 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 practises the table version.

    Step by step

    1. Store the length of nums in n. Both loops run over indexes of nums.
    2. Create dp with Array.fill(n)(1): n ones. No entry is ever below 1, so starting at 1 covers the "element alone" case.
    3. Create best as a var starting at 0. It changes as the loop goes, so it cannot be a val.
    4. Loop over every index i with 0 until n. Each dp(i) needs only entries before it, and they are done by the time the loop reaches i.
    5. Loop over every earlier index j with 0 until i. For i = 0 there are none and the loop does not run.
    6. Check nums(j) < nums(i). The test is strict: an equal value cannot follow, so <= would be wrong.
    7. Update dp(i) to math.max(dp(i), dp(j) + 1). Over all valid j, this keeps the best extension.
    8. Update best with math.max(best, dp(i)) after the inner loop, when dp(i) is final.
    9. Return best as the last expression.

    The solution in Scala

    class Solution {
    def lengthOfLIS(nums: Array[Int]): Int = {
        val n = nums.length
        val dp = Array.fill(n)(1)
        var best = 0
        for (i <- 0 until n) {
            for (j <- 0 until i) {
                if (nums(j) < nums(i)) {
                    dp(i) = math.max(dp(i), dp(j) + 1)
                }
            }
            best = math.max(best, dp(i))
        }
        best
    }
}

    The Scala details worth a closer look:

    • Array.fill(n)(1) builds an array of n elements, each the value in the second parentheses. The array is mutable, so dp(i) = ... changes it in place. The binding itself is a val: the name dp always refers to the same array, but its contents can change.
    • 0 until n stops before n. It is the right range for indexes. 1 to n would run one past the end of the array.
    • math.max takes two Ints and returns the larger one.
    • val and var. n and dp never get a new value, while best does.
    • The last line is the result. best alone, with no return, is what the method gives back.

    Complexity

    Time: O(n²). The two loops look at each pair j < i once, which is n · (n - 1) / 2 pairs. For the largest input, 2500 elements, that is about 3.1 million comparisons.

    Space: O(n). The table dp has one entry per element. Everything else is a few integers.

    Edge cases and common mistakes

    • Returning the last dp entry. For Array(10, 9, 2, 5, 3, 7, 101, 18) the last entry and the maximum happen to match, but for Array(1, 2, 3, 0) the table is 1 2 3 1: the best subsequence, [1, 2, 3], ends at index 2, and the last entry is 1. That is why best tracks the maximum.
    • Using <= instead of <. Equal values would then count as increasing. For seven 7s the table would grow to 1, 2, ..., 7 and the method would return 7 instead of 1.
    • Starting dp at zeros. Every subsequence would come out one too short, and an array with no increasing pair would return 0 instead of 1.
    • Starting best at the wrong value. Starting at 0 is safe because the input has at least one element and every dp(i) is at least 1.
    • A decreasing array. Array(5, 4, 3, 2, 1) gives 1: the table is all ones.
    • A single element. Array(5) gives 1. The inner loop never runs.
    • Confusing subsequence with substring. A subsequence may skip elements. In Array(4, 10, 4, 3, 8, 9) the answer is 3, from [4, 8, 9] or [3, 8, 9], even though those values are not neighbours.

    Testing

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