IncreasingSubsequences
SRM 348 · 2007-05-09 · by soul-net
Problem Statement
A subsequence of a sequence of numbers a is the result of erasing zero or more elements from a. An increasing subsequence is a subsequence in which each element (except the first) is strictly greater than the previous element. An increasing subsequence of a is maximal if unerasing any of the erased elements of a does not result in a longer increasing subsequence.
For example, if a={1,3,2,6,4,5} then {1,3,4} is an increasing subsequence but not a maximal increasing subsequence. {1,2,4,5}, {1,3,4,5}, {1,2,6} and {1,3,6}, on the other hand, are maximal increasing subsequences.
You will be given a as a
Constraints
- a will contain between 1 and 50 elements, inclusive.
- Each element of a will be between 1 and 1000000000 (109), inclusive.
- All elements of a will be distinct.
{1,3,2,6,4,5}
Returns: 4
The example from the problem statement.
{1000000000,100000000,10000000,1000000,100000,10000,1000,100,10,1}
Returns: 10
All maximal increasing subsequences have length 1.
{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}
Returns: 1
Since the whole sequence is an increasing subsequence, there cannot be any other maximal increasing subsequence.
{564,234,34,4365,424,2234,306,21,934,592,195,2395,2396,29345,13295423,23945,2}
Returns: 41
{2,1,4,3,6,5,8,7,11,10,13,12,15,14,17,16,19,18,21,20,23,22,25,24,27,26,29,28,31,30,34,32,36,35,38,37,40,39,42,41,44,43,46,45,48,47,50,49,52,51}
Returns: 33554432
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IncreasingSubsequences with a public method long long count(vector<int> a) · 100 test cases · 2 s / 256 MB per case