Number of Longest Increasing Subsequence

https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/

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

Thoughts

在LIS的基础上要求返回达到最长长度的subseq的个数。我们可以在LIS的基础上多存储一个以nums[i]为结尾的最长subseq的个数，这个值可以在遍历j时得到。

设 Gi: the number of increasing subsequences ending with nums[i] that has len Fi.

注意这道题不能用LIS的方法做. 用题目给的例子[1,3,5,4,7], tails为

[1, 0, 0, 0, 0]

[1, 3, 0, 0, 0]

[1, 3, 5, 0, 0]

[1, 3, 4, 0, 0]

[1, 3, 4, 7, 0]

只知道长度为4的LIS末尾最小值是7, 但不知道前面有多少种可能性, 如1347, 1357等等. 注意tails里的1,3,4,7不一定是条真的LIS.

Code

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, max = 1, res = 0;
        int[] f = new int[n], g = new int[n];

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

        return res;
    }
}

Analysis

Errors:

1. f[i].second = f[j].second;写成了f[i].second = 1;

2. f[i].second += f[j].second;写成了f[i].second += 1;

时间复杂度为内外循环O(n^2)