Best Time to Buy and Sell Stock IV


  • 0
    S

    It is a basic DP question.

    You will need to store maximum profit you can make using a particular number of transactions till a particular day.

    Let's create an array dp[][] where dp[i][j] will represent the maximum profit you can make using i transactions till the end of the jth day.

    This requires a space complexity of O(K x N) where K is the number of transactions and N is the size of the array.

    Also, the maximum transactions which are anyway possible is N/2 as you can purchase a stock and sell it on another day and keep doing it repeatedly.
    (Forget the profits for the time being, focus on the maximum transactions possible)
    Hence this puts an upper limit on the value of K. It has to be less than N/2.

    Now to find the maximum profit which can be made using k transactions till jth day, we have two choices:

    1. Don't do any transaction on the jth day.
      This choice can be represented by dp[k][j] = dp[k][j-1] . i.e. maximum profit which can be made using same number of transactions but till the j-1th day
    2. Sell any stock on jth day.purchased earlier on some ith day in a way that it yields maximum profit.
      This choice can be represented by :
      dp[k][j] = prices[j] - prices[i] + dp[k][i-1].
      This can be found out by maintaining a maxi variable which stores the maximum value of dp[k][i-1]-prices[i]. This maxi variable reduce the time complexity from O(K*N*N) to O(K*N).

    Here is the code representing the same:

    ( Without maxi variable -- Will timeout!!)

    class Solution {
    public:
        int maxProfit(int K, vector<int>& prices) {
            int N=prices.size();
            if(N<=1)return 0;
            K=min(K,(N+1)/2);
            vector<vector<int>>dp(K+1,vector<int>(N+1,0));
           for(int k=1;k<=K;k++){
              for(int j=1;j<N;j++){
                dp[k][j]=dp[k][j-1];
                for(int i=0;i<j;i++){
                  int temp=prices[j]-prices[i];
                  if(i>0)temp+=dp[k-1][i-1];
                  dp[k][j]=max(dp[k][j],temp);
                }
              }
            }
         return dp[K][N-1];
        }
    };
    

    ( With maxi variable -- All test cases passed but Memory Limit Exceeded!!)

    class Solution {
    public:
        int maxProfit(int K, vector<int>& prices) {
            int N=prices.size();
            if(N<=1)return 0;
            K=min(K,(N+1)/2);
            vector<vector<int>>dp(K+1,vector<int>(N+1,0));
           for(int k=1;k<=K;k++){
               int maxi = -prices[0];
               for(int j=1;j<N;j++){
                dp[k][j]=max(dp[k][j-1],prices[j]+maxi);
                maxi=max(maxi,-prices[j]+dp[k-1][j]);
              }
            }
         return dp[K][N-1];
        }
    };
    

    However with little more observation, we can see that we can reduce the space complexity from O(K x Len) to O(2 x Len), since we only need to refer to the i-1th transaction. We can create a dp[2][len] array. dp[i] can be replaced with dp[1] and dp[i-1] with dp[0]. After the jth for loop, we just need to update the dp[0] with dp[1].

    Finally return dp[1][len-1].

    Here is the code indicating this optimization.
    Gets Accepted wihout TLE and without Memory Limit Exceeded. Hurray!!

    class Solution {
    public:
        int maxProfit(int K, vector<int>& A) {
            int N = A.size();
            if(N<=1)return 0;
            K=min(K,(N+1)/2);
            vector<vector<int>>dp(2,vector<int>(N+1,0));
            for(int k=1;k<=K;k++){
              int maxi = -A[0];
              for(int j=1;j<N;j++){
                dp[1][j]=max(dp[1][j-1],A[j]+maxi);
                maxi=max(maxi,-A[j]+dp[0][j]);
              }
              dp[0]=dp[1];
           }
           return dp[1][N-1];
        }
    };
    
    

Log in to reply
 

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