Start learning free

LESSON 453 OF 536 · DYNAMIC PROGRAMMING

Longest Increasing Subsequence in Java: 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

    JAVA · DYNAMIC PROGRAMMING

    Longest Increasing Subsequence in Java, explained

    Problem overview

    The method lengthOfLIS receives an array 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. 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 = [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] works too. No subsequence has 5 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 statement sets O(n²) time and O(n) extra space, with n up to 2500.

    Approach: the best subsequence ending at each index

    Trying every subsequence means looking at 2^n choices, far too many. Instead, ask a smaller question for each position: what is the longest strictly increasing subsequence that ends with nums[i]? Call that number dp[i].

    Every dp[i] is at least 1, because nums[i] alone is a valid subsequence. It can be longer if some earlier element nums[j] (with j < i) is smaller than nums[i]: any subsequence ending at j can be extended by nums[i], giving length dp[j] + 1. Taking the largest of these over all valid j gives dp[i].

    The subsequence can end anywhere, so the final answer is the largest value in dp, not the last one.

    The trace for [10, 9, 2, 5, 3, 7, 101, 18] shows how entries build on each other:

    nums = [10, 9, 2, 5, 3, 7, 101, 18]
dp   = [ 1, 1, 1, 2, 2, 3,   4,  4]

    Here dp[5] = 3 belongs to the 7: it extends the 5 (or the 3), which has dp 2. Then 101 extends that 7 for dp[6] = 4, and 18 does the same. The largest entry is 4.

    The statement mentions a faster O(n log n) method that keeps, for each length, the smallest value a subsequence of that length can end with, and places each element in that list with binary search. This lesson uses the simpler O(n²) table, which is the natural first step.

    Step by step

    1. Store the length of nums in an int named n, because both loops run over the indexes.
    2. Create dp with n entries and fill it with 1 using Arrays.fill. A new int array holds zeros, but every element is a subsequence of length 1 by itself.
    3. Create best starting at 0 to track the largest dp[i] seen.
    4. Loop i over every index from 0 to n - 1. Each dp[i] only needs entries before it, and those are finished by the time the loop reaches i.
    5. Loop j over every earlier index, from 0 to i - 1. Only elements before nums[i] can come before it in a subsequence. For i = 0 the inner loop doesn't run.
    6. Compare the values with nums[j] < nums[i]. The test is strict: an equal value can't follow, so <= would be a bug.
    7. Update dp[i] with Math.max(dp[i], dp[j] + 1). Extending the best subsequence ending at j is one candidate, and the loop keeps the best over all j.
    8. Update best after the inner loop, when dp[i] is final.
    9. Return best after the outer loop.

    The solution in Java

    class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.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 Java details worth a closer look:

    • Arrays.fill(array, value) sets every entry of the array to the value. It lives in java.util, and the lesson's editor already provides that import. In a file of your own, add import java.util.Arrays;.
    • Array defaults. new int[n] starts with zeros. That is why the fill is needed: a zero would wrongly say that an element can't form even a subsequence of one.
    • Math.max takes two int values and returns the larger one, so the update never lowers an entry.
    • No overflow worries. The values in dp never exceed n, and the comparison of nums[j] with nums[i] doesn't do arithmetic, so large element values are safe.

    Complexity

    The two loops look at each pair j < i once, which is n · (n - 1) / 2 pairs, so the time is O(n²). For n = 2500 that is about 3 million comparisons. The dp array holds n integers, so the extra space is O(n).

    Edge cases and common mistakes

    • Returning dp[n - 1]. The longest subsequence need not end at the last element. For [1, 2, 3, 0], the last entry is 1 while the answer is 3. That is why best exists.
    • Using <= instead of <. With all equal values, such as seven 7s, the answer would become 7 instead of 1.
    • Forgetting to start dp at 1. With zeros, every length comes out one too small.
    • Confusing subsequence with subarray. Elements don't have to be neighbours. In [0, 1, 0, 3, 2, 3] the subsequence [0, 1, 2, 3] skips two elements.
    • One element. The inner loop never runs and the answer is 1.

    Testing

    These results come from running the solution:

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