Number of Longest Increasing Subsequence

673. Number of Longest Increasing Subsequence

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

Notice that the sequence has to be strictly increasing.

Given a[] Based on the code of the Longest Increasing Subsequence problem

c[i] The number of the longest increasing subsequence with the last element being a[i]

$c[i]={\sum }_{j=0}^{i}c[j]$ if f[j] has the current longest increasing subsequence

Answer: $Answer={\sum }_{i=0}^{n}c[i],wheref[i]=\underset{0\le j<n}{\max }f[j]$

for (int i = 0; i < n; i++) {
 f[i] = 1;
 c[i] = 1;
 int maxv = 0;
 for (int j = 0; j <= i; j++) {
	if (nums[i] > nums[j]) {
 if (f[j] > maxv) {
 c[i] = c[j];
 maxv = f[j];
 } else if (f[j] == maxv) {
 c[i] += c[j];
 }
	}
 }
 f[i] = maxv + 1;
}