Problem Statement

Given an integer array nums, return the number of longest increasing subsequences.

A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements

Note: Sequences should be strictly increasing.

Examples

1. Example 1:

   • Input: nums = [2, 6, 4, 3, 5]
   • Expected Output: 2
   • Explanation: The longest increasing subsequences are [2, 3, 5] and [2, 4, 5], both having a length of 3. Therefore, there are two such subsequences.

2. Example 2:

   • Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
   • Expected Output: 4
   • Explanation: The longest increasing subsequences are [2, 3, 7, 18], [2, 5, 7, 18], [2, 3, 101], and [2, 5, 101], each having a length of 4. Thus, there are four such subsequences.

3. Example 3:

   • Input: nums = [1, 5, 2, 6, 3, 7]
   • Expected Output: 3
   • Explanation: The longest increasing subsequences are [1, 2, 3, 7], [1, 2, 6, 7], and [1, 5, 6, 7].

Constraints:

• 1 <= nums.length <= 2000
• -10⁶ <= nums[i] <= 10⁶

Try it yourself

Try solving this question here: