Longest Increasing Subsequence

Medium · 1-D Dynamic Programming

You are given an array of integers. Find the length of the longest strictly increasing subsequence, where a subsequence is formed by deleting some (or no) elements without changing the order of the rest. Return that length as an integer.

Examples

Input:  nums = [10,9,2,5,3,7,101,18]
Output: 4
Why:    The subsequence 2,3,7,101 is strictly increasing and has length 4, which is the longest possible.

Input:  nums = [0,1,0,3,2,3]
Output: 4
Why:    The subsequence 0,1,2,3 is strictly increasing and has length 4.

Input:  nums = [7,7,7,7,7,7,7]
Output: 1
Why:    All values are equal, so no two consecutive elements can form an increasing pair, giving a longest length of 1.

Constraints

1 <= nums.length <= 2500, -10^4 <= nums[i] <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Longest Increasing Subsequence

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Longest Increasing Subsequence. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.