Longest Increasing Subsequence

mediumFREEDynamic ProgrammingBlind 75

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example

Input

10,9,2,5,3,7,101,18

Output

Reasoning

Input: nums is a list of 8 integers, 10, 9, 2, 5, 3, 7, 101, 18. A valid subsequence keeps the original order, may skip elements, and each value beats the previous one.
Starting at $10$ or $9$ is weak: only $101$ or $18$ follow and are bigger, so those chains stop at length $2$ .
After $2$ , the values $5$ and $3$ cannot both be used ( $5$ comes first and $5 > 3$ ), so a chain picks one, then reaches $7$ : $2 < 5 < 7$ or $2 < 3 < 7$ .
Likewise $101$ and $18$ clash, so each chain ends with one of them: $2 < 5 < 7 < 101$ or $2 < 3 < 7 < 18$ . All four such chains have length $4$ .
Why not $5$ ? The array splits into decreasing groups $(10, 9, 2)$ , $(5, 3)$ , $(7)$ , $(101, 18)$ ; a chain takes at most one value per group, so $4$ is the ceiling.
Output: 4, a single integer. Notice that equal values never extend a chain, so an array of five $7$ s gives $1$ .

Constraints

1 <= len(nums) <= 2500
-10^4 <= nums[i] <= 10^4

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The Longest Increasing Subsequence problem is a classic example of a problem that can be solved using Dynamic Programming. Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem only once, and storing the solutions to subproblems to avoid redundant computation. In the context of this problem, we need to understand the concept of a subsequence, which is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A strictly increasing subsequence is a subsequence where every element is greater than the previous one.

To approach this problem, it's essential to understand the concept of optimal substructure, which is a property of problems that can be solved using Dynamic Programming. Optimal substructure means that the problem can be broken down into smaller subproblems, and the optimal solution to the larger problem can be constructed from the optimal solutions of the subproblems. In this case, the optimal substructure is the fact that the longest increasing subsequence ending at a particular position is the maximum of the longest increasing subsequences ending at previous positions, plus one if the current element is greater than the previous element.

The longest increasing subsequence problem has many real-world applications, such as finding the longest increasing trend in a stock market or identifying the longest sequence of increasing temperatures in a weather forecast. Understanding the underlying concepts and theory of Dynamic Programming and optimal substructure will help you develop an efficient solution to this problem.

Algorithm/Approach

The general approach to solving this problem involves using a bottom-up Dynamic Programming approach. This involves creating a table to store the lengths of the longest increasing subsequences ending at each position in the input array. The table is filled in a way that each cell represents the length of the longest increasing subsequence ending at that position. The final answer is the maximum value in the table.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a table dp of the same length as the input array nums, where dp[i] represents the length of the longest increasing subsequence ending at position i.
Initialize the table by setting dp[i] = 1 for all i, since a single element is always an increasing subsequence of length 1.
Iterate through the table, and for each position i, compare the current element nums[i] with all previous elements nums[j].
If nums[i] > nums[j], update dp[i] to be the maximum of its current value and dp[j] + 1.
The final answer is the maximum value in the dp table.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Not initializing the table correctly, leading to incorrect values.
Not comparing all previous elements when updating the table, leading to incorrect values.
Not keeping track of the maximum value in the table, leading to an incorrect final answer.

Time & Space Complexity

The expected time complexity of the solution is $O(n^2)$ , where $n$ is the length of the input array, since we are iterating through the table and comparing each element with all previous elements. The expected space complexity is $O(n)$ , since we are using a table of the same length as the input array to store the lengths of the longest increasing subsequences.

solution.py

Python 3.13

Test results