C++, DP with explanation, O(n^2)


  • 8
    Z

    The solution is based on DP.

    For a sequence of numbers,
    cnt[k] is total number of longest subsequence ending with nums[k];
    len[k] is the length of longest subsequence ending with nums[k];
    

    Then we have following equations

    len[k+1] = max(len[k+1], len[i]+1) for all i <= k and nums[i] < nums[k+1];
    cnt[k+1] = sum(cnt[i]) for all i <= k and nums[i] < nums[k+1] and len[i] = len[k+1]-1;
    

    Starting case and default case: cnt[0] = len[0] = 1;

    class Solution {
    public:
        int findNumberOfLIS(vector<int>& nums) {
            int n = nums.size(), maxlen = 1, ans = 0;
            vector<int> cnt(n, 1), len(n, 1);
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        if (len[j]+1 > len[i]) {
                            len[i] = len[j]+1;
                            cnt[i] = cnt[j];
                        }
                        else if (len[j]+1 == len[i]) 
                            cnt[i] += cnt[j];
                    }
                }
                maxlen = max(maxlen, len[i]);
            }
            // find the longest increasing subsequence of the whole sequence
           // sum valid counts
            for (int i = 0; i < n; i++) 
                if (len[i] == maxlen) ans += cnt[i];
            return ans;
        }
    };
    
    

  • 0
    J

    Thanks for sharing the elegant code!


  • 0
    B
    This post is deleted!

  • 0
    B

    @zestypanda One qq - you say in the equation:

    len[k+1] = max(len[k+1], len[i]+1), but you check only for len[k+1] = max(len[k+1], len[i]) in the code. Why so?


  • 0
    B

    @BatCoder said in C++, DP with explanation, O(n^2):

    @zestypanda One qq - you say in the equation:

    len[k+1] = max(len[k+1], len[i]+1), but you check only for len[k+1] = max(len[k+1], len[i]) in the code. Why so?

    the place you mentioned in the code is for output. in the code, it is

    if (len[j]+1 > len[i]) {
        len[i] = len[j]+1;
        cnt[i] = cnt[j];
    }
    

  • 0
    B

    @beetlecamera Sorry, could you please elaborate? What output do you mean?


  • 0
    Z

    @BatCoder Sorry, I am not sure whether I follow your question. The equation is for DP. After DP, you get the count and length of longest sequence ending with nums[k]. However, it may not be the longest one in the whole sequence. You have to find the max value of all len[k] for k = 1...n, and sum the valid count.


  • 0
    B

    @zestypanda Small point:

    The last two tasks can be done in a single for loop. You don't need two separate for loops to do that (I was asked this smalloptimization in an interview once).

            for(int i= 0; i<n; i++) {
                if(len[i]>maxlen) {
                    maxlen=len[i];
                    ans=0;
                }
                if(len[i]==maxlen)
                    ans+=cnt[i];
            }
    

  • 0
    Z

    @BatCoder Thank you! I have incorporated your suggestion.


  • 0
    T

    I am confused that why this is not right? I feel I did the same thing as you did:

        public int findNumberOfLIS(int[] nums) {
            if(nums==null || nums.length<1){
                return 0;
            }        
            if(nums.length==1){
                return 1;
            }
            int[] dp = new int[nums.length];
            dp[0]=1;
            int max = 1;
            for(int i=1;i<nums.length;i++){
                dp[i]=1;
                for(int j=0;j<i;j++){
                    if(nums[i]>nums[j]){
                        dp[i] = Math.max(dp[i],dp[j]+1);
                    }
                }
                
                max = Math.max(max,dp[i]);
            }
            Map<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<nums.length;i++){
                if(dp[i]==1){
                    map.put(1,map.getOrDefault(1,0)+1);
                }else{
                    map.put(dp[i],map.getOrDefault(dp[i],0)+map.get(dp[i]-1));
                }
            }
            return map.get(max);
        }
    
    

  • 1
    X

    @tiandiao123

    map.put(dp[i],map.getOrDefault(dp[i],0)+map.get(dp[i]-1));

    This line in your code is incorrect, which causes your code generate a larger number. You can't directly add map.get(dp[i]-1) there, since the last element of previous subsequence with length dp[i]-1 may not be less than nums[i], so there is not increasing sequence here. For instance, with the input [1,2,4,3,5,4,7], dp[5] = 4, however previous subsequence with length 3 [1,2,4] can't form a subsequence [1,2,4,4] with nums[5].


  • 0
    T

    @xy1994 Oh,Got it!!! You are right, thank you!!!


  • 0
    N

    @zestypanda Hello, I read your solution and I can't understand a part of it.
    Could you please explain the line

    else if (len[j]+1 == len[i]) 
        cnt[i] += cnt[j];
    

    The way I interpret the statement is, for a value nums[j] which is greater is than nums[i], if the len[j] + 1 == len[i], increase the count at i .

    I don't understand how len[i] will be greater than len[j] if nums[j] is greater than
    or equal to nums[i]. Could you provide an example of such a case please ?

    Thank you.


  • 0
    Z

    @nightfox_lemarc len[j] is initially 1, and it is NOT the max length until the end of the loop.
    For example, the numbers are

    1, 2, 4, 6;
    

    During the loop, len[3] will change from 1 to 2, then to 3, then to 4.


  • 0
    Q

    @zestypanda said in C++, DP with explanation, O(n^2):

    else if (len[j]+1 == len[i])
    cnt[i] += cnt[j];

    Could you explain these two lines? Thank you.


Log in to reply
 

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