Leetcode 673: Number of Longest Increasing Subsequence

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

Notes:

This question can be viewed as a follow-up to the longest increasing subsequence (LIS).

The key is to use another dp array to memorize the number of the longest LIS ending with the ith element: dp[i]

When we find val[i] > val[j], the dp[i] should be updated by dp[j]. (why? see below)

The logic is very straightforward: there are dp[j] LIS ending with the jth element, so now there should be the same number of LIS ending with the ith element.

Another detail is that we need to update the longest LIS as we scan through the array. When the current longest length equals to the previous longest length, we need to add them up; if current is longer, we need to replace the previous one with the current.

The T-C is O(N^2), and the S-C is O(N).

See the code below:

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int res = 1, len = nums.size(), pre_maxL = 1;
        vector<int> dp1(len, 1), dp2(len, 1);
        //dp1[i]: the maximum length of the increasing subsequence ending with the ith element;
        //dp2[i]: the number of the LIS ending with the ith element; 
        for(int i=1; i<len; ++i) {
            int cur_ct = 1, cur_maxL = 1;
            for(int j=0; j<i; ++j) {
                if(nums[i] > nums[j]) {
                    dp1[i] = max(dp1[i], dp1[j] + 1);
                    if(cur_maxL < dp1[i]) {
                        cur_maxL = dp1[i];
                        cur_ct = dp2[j];
                    }
                    else if(cur_maxL == dp1[j] + 1) cur_ct += dp2[j]; //need to compare with dp1[j]+1, not dp1[i]
                }
            }
            dp2[i] = cur_ct;
            if(cur_maxL > pre_maxL) {
                pre_maxL = cur_maxL;
                res = cur_ct;
            }
            else if(cur_maxL == pre_maxL) res += cur_ct;
        }
        return res;
    }
};