Google Online Assessment (OA) - Minimum Number of Decreasing Subsequence Partitions
Given an integer array, split it into strictly decreasing subsequences. Return the minimum number of decreasing subsequences you can get from splitting the array. A subsequence keeps the original relative order but does not need to be contiguous.
Examples
Example 1:
Input:
[5, 2, 4, 3, 1, 7]
Output: 3
Explanation:
The array can be split into [5, 2, 1], [4, 3], [7] to get 3 decreasing subsequences. Or it can be split into [5, 4, 3], [2, 1], [7] to also get 3 decreasing subsequences.
The partition into [5, 4, 3, 2, 1], [7] is not valid because 5, 4, 3, 2, 1 do not appear in that order in the original array; a subsequence must keep the original relative order.
Example 2:
Input:
[2, 9, 13, 14, 4, 8, 7, 6, 10]
Output: 4
Explanation:
[2], [9, 4], [13, 10], [14, 8, 7, 6]
Example 3:
Input:
[6, 6, 6]
Output: 3
Explanation:
[6], [6], [6]