LISNumberDivTwo
SRM 585 · 2013-06-25 · by wrong
SRM 585 · 2013-06-25 · by wrong · Simple Search, Iteration
Problem Statement
Problem Statement
Let A be a sequence of integers. We want to create this sequence as a concatenation of some (one or more) strictly increasing sequences. The LISNumber of A is the smallest number of strictly increasing sequences we need.
For example, the LISNumber of the sequence A = {1, 4, 4, 2, 6, 3} is 4, since A can be created as {1, 4} + {4} + {2, 6} + {3}, and there is no way to create A by concatenating 3 (or fewer) strictly increasing sequences.
Another example: The LISNumber of the sequence B = {10, 20, 30} is 1, since B is already a strictly increasing sequence.
Note that the optimal way of writing a sequence as a concatenation of some strictly increasing sequences is always unique.
You are given aint[] seq. Return the LISNumber of the sequence seq.
For example, the LISNumber of the sequence A = {1, 4, 4, 2, 6, 3} is 4, since A can be created as {1, 4} + {4} + {2, 6} + {3}, and there is no way to create A by concatenating 3 (or fewer) strictly increasing sequences.
Another example: The LISNumber of the sequence B = {10, 20, 30} is 1, since B is already a strictly increasing sequence.
Note that the optimal way of writing a sequence as a concatenation of some strictly increasing sequences is always unique.
You are given a
Constraints
- seq will contain between 1 and 50 elements, inclusive.
- Each element of seq will be between 1 and 50, inclusive.
Examples
0)
{1, 4, 4, 2, 6, 3}
Returns: 4
This is the example from the problem statement.
1)
{5, 8, 9, 12, 16, 32, 50}
Returns: 1
In this case, seq itself is already strictly increasing. Thus, the LISNumber of this sequence is 1.
2)
{1, 1, 9, 9, 2, 2, 3, 3}
Returns: 6
{1, 1, 9, 9, 2, 2, 3, 3} = {1} + {1, 9} + {9} + {2} + {2, 3} + {3}
3)
{50, 40, 30, 20, 10}
Returns: 5
4)
{42}
Returns: 1
Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LISNumberDivTwo with a public method int calculate(vector<int> seq) · 80 test cases · 2 s / 256 MB per case