NUMBER OF LONGEST INCREASING SUBSEQ. SEGMENT TREE HARD

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


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

Notice that the sequence has to be strictly increasing.



Example 1:

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

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


Constraints:

1 <= nums.length <= 2000
-10^6 <= nums[i] <= 10^6

--------------------------------------------------------------------------------------------------------------------------------------
DYNAMIC PROGRAMMING O(N * N)

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums){
        int n=nums.size();
        vector<int> dp(n,1);
        vector<int> count(n,1);
        for(int end=1;end<n;end++){
            for(int start=0;start<end;start++){
                if(nums[end]>nums[start]){
                    if(dp[start]+1>dp[end]){
                        dp[end]=1+dp[start];
                        count[end]=count[start];
                    }
                    else if(dp[start]+1==dp[end]){
                        count[end]+=count[start];
                    }
                }
            }
        }
        int res=0;
        int LIS=*max_element(dp.begin(),dp.end());
        for(int i=0;i<dp.size();i++){
            if(dp[i]==LIS){
                res+=count[i];
            }
        }
        return res;
    }
};

---------------------------------------------------------------------

Segment Tree

class Solution {
private:
    vector<pair<int,int>> tree; // pair<int,int> = length,ways
public:
    pair<int,int> chooseBest(pair<int,int> &left, pair<int,int> &right){
        pair<int,int> res;

        int mxLen_LFT=left.first;
        int ways_LFT=left.second;

        int mxLen_RHT=right.first;
        int ways_RHT=right.second;

        if(mxLen_LFT > mxLen_RHT){
            res={mxLen_LFT , ways_LFT};
        }
        else if(mxLen_LFT < mxLen_RHT){
            res={mxLen_RHT , ways_RHT};
        }
        else{
            res.first=mxLen_LFT;
            res.second=ways_LFT+ways_RHT;
        }
        return res;
    }

    void update(int start, int end, int parent, int index, int mxLength, int ways){
        if(start==end){
            if(tree[parent].first==mxLength){ // if same maxlength is achieved again, add ways
                tree[parent].second+=ways;
            }
            else{  // if achieved more length, update length and ways
                tree[parent]={mxLength,ways};
            }
            return;
        }
        int mid=(start+end)/2;
        if(index<=mid){
            update(start,mid,2*parent+1,index,mxLength,ways);
        }
        else{
            update(mid+1,end,2*parent+2,index,mxLength,ways);
        }
        tree[parent]=chooseBest(tree[2*parent+1],tree[2*parent+2]);
    }

    pair<int,int> maxLen(int start, int end, int l, int r, int parent){
        if(start>r || end<l){
            return {0,0};
        }
        if(start>=l && end<=r){
            return tree[parent];
        }
        int mid=(start+end)/2;
        pair<int,int> left=maxLen(start,mid,l,r,2*parent+1);
        pair<int,int> right=maxLen(mid+1,end,l,r,2*parent+2);
        return chooseBest(left,right);
    }

    int findNumberOfLIS(vector<int>& nums) {
        vector<pair<int,int>> new_nums;
        for(int i=0;i<nums.size();i++){
            new_nums.push_back({nums[i],i});
        }

        sort(new_nums.begin(),new_nums.end());

        unordered_map<int,int> rank;
        int mx=0;
        for(int i=0;i<nums.size();i++){
            if(rank.find(new_nums[i].first)==rank.end()){
                nums[new_nums[i].second]=mx;
                rank[new_nums[i].first]=mx;
                mx++;
            }
            else{
                nums[new_nums[i].second]=rank[new_nums[i].first];
            }
        }

        /*
            cout<<"Your new array -> ";
            for(auto c: nums){
                cout<<c<<" ";
            }
            cout<<endl<<endl;
       */

        tree.resize(4*mx+5);

        for(int i=0;i<nums.size();i++){
        /* As each element can be a subseq in itself with len=1 and way=1 to form itself*/
            int mxLen=1;  // mxLen- maximum length achieved for this index
            int ways=1;  // ways- number of ways to achieve mxLen at this index

            if(nums[i]>0){
                pair<int,int> info=maxLen(0,mx,0,nums[i]-1,0);
                if(info.first+1>mxLen){
                    mxLen=info.first+1;
                    ways=info.second;
                }
            }

            /*
            cout<<"largest increasing length ending at index- "<<i<<" is "<<mxLen<<endl;
            cout<<"Number of ways, incs subsq. of len= "<<mxLen<<" ending at index "<<i<<" is "<<ways<<endl<<endl;
            */

            update(0,mx,0,nums[i],mxLen,ways);
        }
        return tree[0].second;
    }
};