Skip to content
BASA DSA

Longest Increasing Subsequence

Medium1-D Dynamic Programming

Return the length of the longest strictly increasing subsequence. Selected indices must increase but need not be adjacent.

Example 1

Input
nums = [3,1,2,5,4,7]
Output
4

Explanation

1,2,4,7 gives length four; a subsequence may skip indices.

Example 2

Input
nums = [2,2,2]
Output
1

Explanation

Equal values cannot extend a strict increase, giving length one.

Example 3

Input
nums = [9,7,5]
Output
1

Explanation

Every later value is smaller, so only singleton subsequences increase.

Constraints

  • 1 <= len(nums) <= 2500
  • Values are -10000..10000

Function contractlengthOfLISArguments: json
Loading draft…
SolutionRuns on your device