मुख्य कंटेंट तक स्किप करें
Back to ChallengesLongest Increasing Subsequence (LIS)Medium 25 min

Longest Increasing Subsequence (LIS)

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

Examples

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
The longest increasing subsequence is [2,3,7,101], length 4.
Input: nums = [0,1,0,3,2,3]
Output: 4
The longest increasing subsequence is [0,1,2,3].

Constraints

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

Complexity Analysis

Time
O(n^2)
nested loop DP. Note that O(n log n) is possible using binary search.
Space
O(n)
DP array.

Test Cases

#1 Standard LIS
Input: [10,9,2,5,3,7,101,18]
Expected: 4
#2 Array with duplicate values
Input: [0,1,0,3,2,3]
Expected: 4
#3 All identical values
Input: [7,7,7,7,7]
Expected: 1
Output
Click "Run Code" to see output here...