TopCoder problem "IncreasingSubsequences" used in SRM 348 (Division II Level Three)



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 int[] representing a sequence of distinct numbers. Return the number of maximal increasing subsequences it contains.

 

Definition

    
Class:IncreasingSubsequences
Method:count
Parameters:int[]
Returns:long
Method signature:long count(int[] a)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
{1,3,2,6,4,5}
Returns: 4
The example from the problem statement.
1)
    
{1000000000,100000000,10000000,1000000,100000,10000,1000,100,10,1}
Returns: 10
All maximal increasing subsequences have length 1.
2)
    
{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.
3)
    
{564,234,34,4365,424,2234,306,21,934,592,195,2395,2396,29345,13295423,23945,2}
Returns: 41

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7753

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10672&pm=7753

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Dynamic Programming