29. Leetcode 673. Number of Longest Increasing Subsequence.md

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.

---

Solutions

Solution2 - DP

/*
Method2: DP
The idea is to use DP for getting longest subsequence;
We record the number of longest subsequences in the process.

DP for getting longest subsequence:
let A be an unsoted array of integers
let dp[i] be the longest subsequence ending with A[i], then
dp[i] = max(dp[j]+1), for all j < i and A[i] > A[j]

T(n) = O(n^2)
S(n) = O(n)
*/
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int len = nums.size();
        /*
        initialize to all 1 is for the sepecial case:
        [2,2,2,2,2]
        */
        vector<int> dp(len,1);//length of longest subsequence ending at A[i]
        vector<int> count(len,1);//# of longest subsequence ending at A[i]
        int Max = 0;
        int cnt = 0;
        for(int i = 0; i < len; i++){
            for(int j = i-1; j >=0; j--){
                if(nums[i] > nums[j]){
                    if(dp[i]-1 < dp[j]){
                        dp[i] = dp[j]+1;
                        count[i] = count[j];
                    }
                    else if(dp[i]-1 == dp[j]){
                        count[i] += count[j];
                    }
                }
            }
            /////
            if(Max < dp[i]){
                Max = dp[i];
                cnt = count[i];
            }
            else if(Max == dp[i]){
                cnt += count[i];
            }
        }
        return cnt;
    }
};

---

Solution1 - Brute Force

/*
Method1: Brute Force
//T(n) = O(2^n)
*/
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if(nums.empty()){return 0;}
        int len = nums.size();
        unordered_set<string>count;
        string each = "";
        find(nums, 0, INT_MIN, each, count);
        return count.size();
    }
    void find(vector<int>& nums, int pos, int last, string& each, unordered_set<string>& count){
        if(pos == nums.size()){
            if(count.empty()){
                count.insert(each);
            }
            else{
                string tmp = *count.begin();
                if(tmp.size() == each.size()){
                    count.insert(each);
                }
                else if(tmp.size() < each.size()){
                    count.clear();
                    count.insert(each);
                }
            }

        }else{
            for(int i = pos; i < nums.size(); i++){
                //consider current i
                if(nums[i] > last){
                    string tmp = to_string(i);
                    each+=tmp;
                    find(nums, i+1, nums[i], each, count);
                    int size = tmp.size();
                    while(size--)
                        each.pop_back();
                }
                //not consider current i
                find(nums, i+1, last, each, count);
            }
        }
    }
};