class Solution {
public:
    int result = 0;
    vector<int> path;
    int max_path = 0;
    void track_back(vector<int>& nums , int indnx)
    {
        if(path.size() > max_path)
        {
            max_path = path.size();
            result = 1;
        }else if(path.size() == max_path) result++;
        if(indnx >= nums.size() ) return;
        for(int i = indnx ;i<nums.size();i++)
        {
            if( (path.size() == 0)||(path.size() !=0 && nums[i] > path[path.size()-1]) ) 
            {
                path.push_back(nums[i]);
                track_back(nums,i+1);
                path.pop_back();
            }
        }
        return;
    }
    int findNumberOfLIS(vector<int>& nums) {
        track_back(nums,0);
        return result;
    }
};

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);//i以内的最长子序列
        vector<int> count(nums.size(),1);//i以内最长子序列的个数
        int max_long = 1;
        for(int i=1 ; i<nums.size() ;i++)
        {
            for(int j=0 ; j<i ; j++)
            {
                if(nums[i] > nums[j] && dp[i] < dp[j] + 1) //发现更长的最长子序列
                {
                    count[i] = count[j]; 
                    dp[i] =  dp[j] + 1;
                }else if(nums[i] > nums[j] && dp[i] == dp[j] + 1) //发现和当前最长一样长的
                {
                    count[i] += count[j];
                    dp[i] = dp[i];
                }else if(nums[i] > nums[j] && dp[i] <= dp[j] + 1) //没发现最长的
                {
                    dp[i] = dp[i];
                }
                if(dp[i] > max_long) max_long = dp[i];
            }
        }
        int result = 0;
        for(int i=0 ; i<nums.size() ;i++)
            if(dp[i] == max_long) result += count[i];
        return result;
    }
};