problem300

package
v1.6.6 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 27, 2021 License: MIT Imports: 0 Imported by: 0

README

< Previous                  Next >

300. Longest Increasing Subsequence (Medium)

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 

Example 1:

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

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

 

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

 

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

[Array] [Binary Search] [Dynamic Programming]

Similar Questions

  1. Increasing Triplet Subsequence (Medium)
  2. Russian Doll Envelopes (Hard)
  3. Maximum Length of Pair Chain (Medium)
  4. Number of Longest Increasing Subsequence (Medium)
  5. Minimum ASCII Delete Sum for Two Strings (Medium)
  6. Minimum Number of Removals to Make Mountain Array (Hard)
  7. Find the Longest Valid Obstacle Course at Each Position (Hard)

Documentation

The Go Gopher

There is no documentation for this package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL