← 返回 salesforce 的题目列表Longest Increasing Subsequence
类型：online_judge
Longest Increasing Subsequence
Given an unsorted integer array nums, return the length of its longest strictly increasing subsequence.
A subsequence does not need to be contiguous, but it must preserve the relative order of elements.
In the interview, explain in order:
A brute-force solution with its time and space complexity;
An optimal solution with its time and space complexity;
An implementation of the optimal solution.
Input Format
First line: integer n, the array length.
Second line: n integers representing nums.
Output Format
Print one integer: the length of the longest strictly increasing subsequence.
Constraints
1 <= n <= 2500
-10^4 <= nums[i] <= 10^4
Example 1
Input:
8
10 9 2 5 3 7 101 18
Output:
4
One longest strictly increasing subsequence is [2, 3, 7, 101].
Example 2
Input:
6
0 1 0 3 2 3
Output:
4
Example
Input
8
10 9 2 5 3 7 101 18
Output
4