Sunday, September 9, 2018

Best time to buy and sell the stock - Multiple Transaction

Best time to buy and sell the stock : 

Multiple Transaction : 
If 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 as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note:  you must sell the stock before you buy again

Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buyIdx     = 0;
        int currProfit = 0;
        int profit     = 0;
        int maxProfit  = 0;
        
        for (int i = 1; i < prices.size(); i++)
        {
            currProfit = prices[i] - prices[buyIdx];
            
            if (currProfit > profit)
            {
                profit = currProfit;
            }
            else 
            {
                buyIdx = i;
                maxProfit += profit;
                profit = 0;
            }
        }
        
        maxProfit += profit;

        return maxProfit;
    }
};

No comments:

Post a Comment