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.
|