best time to buy and sell stock dynamic programming

3
votes

Trying to solve this: Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Solution: What i am doing is divide and conquer kind of approach.

dp[i][j] is the maximum profit between ith and jth day.Calculated as below:

dp[i][j] = max(dp[i][j], max(prices[i] - prices[j], dp[k][j], dp[i][k+1])), where k is less than i and greater than j.

Now all we need is below to find out the maximum profit in two transactions:

m = max(m, max(dp[i][j], dp[k][j] + dp[i][k+1]))

Please give me just hint to solve this problem as the existing solution presented here is timing out.

class Solution(object):
    def profit(self, prices, dp):
        m = 0
        for w in range(1, len(prices)):
            for i in range(1, len(prices)):
                for j in range(i-w, i):
                    if i-w < 0:
                        continue
                    for k in range(j, i):
                        dp[i][j] = max(dp[i][j], max(prices[i] - prices[j], dp[k][j], dp[i][k+1]))
                        m = max(m, max(dp[i][j], dp[k][j] + dp[i][k+1]))
        return m

    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        dp = [[0 for i in range(len(prices)+1)] for i in range(len(prices)+1)]
        return self.profit(prices, dp)
2
pythonalgorithmdynamic-programming
Do you mean the max profit if you buy first and sell later? Because otherwise it's just the min and the max. – Carlos
@Carlos: yes, buy first and then sell later. – noman pouigt

2 Answers

2
votes

A hint would be to pre-process the prices and find out the maximum profit that can be earnt by selling at a price ending at index i. Then, you can start from end of the pre-process vector to find out the solution to the problem. This will solve the problem using 1-D DP and will not time out.

  int maxProfit(vector<int>& prices) {

    int mprof = 0;
    if (prices.size()>1){
        int maxprof = 0;
        vector<int> mp; // max profit before each element
        mp.push_back(0);
        int st = *prices.begin();
        for(int i = 1 ; i<=prices.size();i++){  //compute mp vector
            if (mprof < prices[i]-st){mprof = prices[i]-st;}
            if (prices[i]<st){st = prices[i];}
            mp.push_back(mprof);
        }
        mprof = 0;
        int ed = *(prices.end()-1);
        for (int i = prices.size()-2; i>=0; i--){
            if (mprof < ed - prices[i] + mp[i]) { mprof = ed - prices[i] + mp[i];}
            if (prices[i]>ed) {ed = prices[i];}
        }
    }
    return mprof;

}
0
votes
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0

        max_profit = 0
        buy_price = prices[0]
        for price in prices:
            if price >= buy_price:
                max_profit += price - buy_price
                buy_price = price
            else:
                buy_price = price


        return max_profit