[673. Number of Longest Increasing Subsequence] C++ AC Time: O(n^2), Space: O(n)


  • 0

    Is it real DP problem???

    Two vectors:
    vector 1: store the longest length from the start to current position
    vector 1: store the number of longest length from start to current position

    class Solution {
    public:
    int findNumberOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> dp_len(nums.size(), 1);
        vector<int> dp_cnt(nums.size(), 1);
        int res_len = 1;
        int res_cnt = 1;
        for(int i = 1; i < nums.size(); ++i){
            int j = i-1;
            int temp_len = 1;
            int temp_cnt = 1;
            while(j >= 0){
                if(nums[j] < nums[i]){
                    int new_len = dp_len[j] + 1;
                    if(temp_len < new_len){
                        temp_len = new_len;
                        temp_cnt = dp_cnt[j];
                    }else if(temp_len == new_len){
                        temp_cnt += dp_cnt[j];
                    }
                }
                j--;
            }
            dp_len[i] = temp_len;
            dp_cnt[i] = temp_cnt;
            if(dp_len[i] > res_len){
                res_len = dp_len[i];
                res_cnt = dp_cnt[i];
            }else if(dp_len[i] == res_len){
                res_cnt += dp_cnt[i];
            }
        }
        return res_cnt;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.