FastPrep

Description

Solutions

Decreasing Subsequences

🤘 INTERN📚RELATED PROBLEMS

Given an int array nums of length n. Split it into strictly decreasing subsequences. Output the min number of subsequences you can get by splitting.

Example 1:

Input:  nums = [5, 2, 4, 3, 1, 6]
Output: 3 
Explanation:
You can split this array into: [5, 2, 1], [4, 3], [6]. And there are 3 subsequences you get.
Or you can split it into [5, 4, 3], [2, 1], [6]. Also 3 subsequences.
But [5, 4, 3, 2, 1], [6] is not legal because [5, 4, 3, 2, 1] is not a subsequence of the original array.

Example 2:

Input:  nums = [2, 9, 12, 13, 4, 7, 6, 5, 10]
Output: 4 
Explanation:
You can split the array into: [2], [9, 4], [12, 10], [13, 7, 6, 5].

Example 3:

Input:  nums = [1, 1, 1]
Output: 3 
Explanation:
Because of the strictly descending order you have to split it into 3 subsequences: [1], [1], [1].

Constraints:

Unknown yet. If you happen to know about it, feel free to lmk! TYSM ~3~