Start learning free

LESSON 456 OF 539 · DYNAMIC PROGRAMMING

Longest Increasing Subsequence in C#: O(n^2) 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

    C# · DYNAMIC PROGRAMMING

    Longest Increasing Subsequence in C#, explained

    Problem overview

    LengthOfLIS receives an int[] named nums and returns the length of its longest strictly increasing subsequence. A subsequence keeps some elements, possibly all or none removed, in their original order. Strictly increasing means every element is larger than the one before it, so equal values cannot both be used.

    For {10, 9, 2, 5, 3, 7, 101, 18} the answer is 4. One such subsequence is 2, 3, 7, 101, and 2, 5, 7, 18 is another. For {7, 7, 7, 7, 7, 7, 7} the answer is 1, because equal values do not increase.

    Approach: best subsequence ending at each index

    Checking every subsequence is hopeless: 2500 elements have an astronomical number of them (2 to the power 2500) of them. Define a smaller problem instead: dp[i] is 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. If nums[j] < nums[i], then nums[i] can be appended to the best subsequence that ends at j, giving length dp[j] + 1. Keep the largest such value. If no earlier element is smaller, dp[i] stays 1.

    The answer is the largest dp[i], not the last one: the best subsequence can end anywhere. For {10, 9, 2, 5, 3, 7, 101, 18} the table is:

    dp = [1,1,1,2,2,3,4,4]

    The 3 at index 4 ends a subsequence of length 2 (2, 3), the 7 ends one of length 3 (2, 3, 7), and both 101 and 18 end ones of length 4. The maximum is 4.

    This lesson uses this simple table; a faster method is described after the complexity section.

    Step by step

    1. Store nums.Length in n. Both loops run over the indexes of nums.
    2. Create dp as new int[n] and fill it with 1 using Array.Fill(dp, 1). A new int array holds zeros, but no entry should be below 1.
    3. Create best, starting at 0. It tracks the largest dp[i] seen.
    4. Loop i from 0 to n - 1. Each dp[i] needs only entries before it, and those are final by then.
    5. Loop j from 0 to i - 1. Only elements before nums[i] can precede it. For i = 0 the loop does not run.
    6. Check nums[j] < nums[i]. It is <, not <=, because the subsequence must be strictly increasing.
    7. Update dp[i] with Math.Max(dp[i], dp[j] + 1).
    8. After the inner loop, update best with Math.Max(best, dp[i]). By then dp[i] has seen every j.
    9. Return best after the outer loop.

    The solution in C#

    class Solution {
    public int LengthOfLIS(int[] nums) {
        int n = nums.Length;
        int[] dp = new int[n];
        Array.Fill(dp, 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] = Math.Max(dp[i], dp[j] + 1);
                }
            }
            best = Math.Max(best, dp[i]);
        }
        return best;
    }
}

    The C# details worth knowing:

    • Array.Fill(dp, 1) sets every element of an array to one value. It lives in the System namespace, like Math.Max.
    • An int[] is a fixed-length array whose elements start at 0. Without the fill, every dp[i] would be one too small.
    • Math.Max(a, b) returns the larger of two numbers; there is no need for an if.

    Complexity

    Time: O(n^2). 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 three million comparisons.

    Space: O(n) for the dp array.

    A faster way: O(n log n)

    Keep a list tails in which entry k is the smallest value that an increasing subsequence of length k + 1 can end with. The list is always sorted, so each new element finds its place by binary search: if it is larger than everything, it extends the list by one (a longer subsequence exists); otherwise it replaces the first entry that is at least as large, which keeps that length's ending value as small as possible. The answer is the length of the list.

    public int LengthOfLIS(int[] nums) {
    List<int> tails = new List<int>();
    foreach (int x in nums) {
        int pos = tails.BinarySearch(x);
        if (pos < 0) pos = ~pos;
        if (pos == tails.Count) tails.Add(x); else tails[pos] = x;
    }
    return tails.Count;
}

    List<T>.BinarySearch returns the index of an equal element if there is one, and otherwise the bitwise complement (~) of the index where the value would be inserted. The line if (pos < 0) pos = ~pos; turns both cases into a position. Because an equal element is replaced by itself, equal values never lengthen the list, which keeps the subsequence strictly increasing. On {10, 9, 2, 5, 3, 7, 101, 18} the list evolves like this:

    10 -> [10]
9 -> [9]
2 -> [2]
5 -> [2,5]
3 -> [2,3]
7 -> [2,3,7]
101 -> [2,3,7,101]
18 -> [2,3,7,18]

    Only the length of the list is the answer: in general its entries can come from different subsequences, so the list itself need not be one. Here its length, 4, is right. For the other test inputs it returns 4, 1, 1 and 3, matching the table method.

    Edge cases and common mistakes

    • One element. {5} returns 1. The inner loop never runs, so dp[0] stays 1, and best becomes 1.
    • Decreasing input. {4, 3, 2, 1} returns 1: no element is smaller than a later one.
    • Already increasing. {1, 2, 3, 4} returns 4.
    • Equal values. {7, 7, 7, 7, 7, 7, 7} returns 1. Using <= would return 7.
    • Returning dp[n - 1]. For {10, 9, 2, 5, 3, 7, 101, 18} that happens to be 4, but for {1, 2, 3, 0} the last entry is 1 while the answer is 3. Take the maximum.
    • Subsequence versus substring. The chosen elements need not be next to each other.

    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.
    • {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