[LeetCode] 673. Number of Longest Increasing Subsequence

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Thought process:

DP. 

1. Sub-problem: find the number and length of the longest increasing subsequence ending at index i.
2. Function:
1. f[i] = max(f[0,...,i] where nums[j] < nums[i]) + 1 or 1 if no nums[0,...,i] is less than nums[i].
2. counts[i] = sum(counts[0,...i]) where f[j] = max(f[0,...,i]) where nums[j] < nums[i].
3. Initialization: f[0] = 1. counts[0] = 1.
4. Answer: max(counts) where f[i] == max(f).

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class Solution { public int findNumberOfLIS(int[] nums) { int len = nums.length; if (len == 0) { return 0; } int[] f = new int[len]; int[] counts = new int[len]; f[0] = 1; counts[0] = 1; int max = 1; int total = 1; for (int i = 1; i < len; i++) { int longest = 1; int count = 1; for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { if (f[j] + 1 == longest) { count += counts[j]; } else if (f[j] + 1 > longest) { longest = f[j] + 1; count = counts[j]; } } } f[i] = longest; counts[i] = count; if (max == longest) { total += counts[i]; } else if (max < longest) { max = longest; total = counts[i]; } } return total; } }

Time complexity: O(n^2).