IncreasingSubsequences | Topcoder Archive

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

```
{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

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.