Longest Increasing Subsequence

Languages

Given an array of integers numbers, determine the length of the longest subsequence in which each number is strictly greater than the one before it.

A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, the subsequences of [1, 2, 3] are [1], [2], [3], [1, 2], [2, 3], [1, 3], and [1, 2, 3].

Input

  • numbers: number[]: An array of integers

Examples

Input: numbers = [0,1,0,3,2,3]
Output: 4
Explanation: The longest increasing subsequence is [0, 1, 2, 3], which has a length of 4.
Input: numbers = [3,2]
Output: 1
Explanation: The longest increasing subsequence is either [3] or [2], both of which have a length of 1.
Input: numbers = [3,3,3,3]
Output: 1
Explanation: The longest increasing subsequence is [3], since all elements are the same.

Constraints

  • 1 <= numbers.length <= 2500
  • -10,000 <= numbers[i] <= 10,000