Maximize profit from buying and selling stocks with multiple transactions

Question

I am working on a problem where I need to maximize profit from buying and selling stocks with multiple transactions. The task is to find and return the maximum profit achievable given an integer array prices, where prices[i] is the price of a stock on the ith day.

Examples:

Example 1:

Input: prices = [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. Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

I have implemented a solution in Java, but it's not giving the correct output for all cases. Here's the current implementation:

class Solution {
    public int maxProfit(int[] prices) {
        int overall_profit = 0;
        boolean isBought = false;
        int track = 0;
        for(int i = 0; i < prices.length - 1; i++){
            int profit = 0;
            if(prices[i+1] > prices[i]){
                profit += prices[i+1] - prices[i];
                if(!isBought){
                    isBought = true;
                    track = i;
                }
                i++;
            }
            if(profit > overall_profit){
                overall_profit = profit;
            }
            if(isBought){
                isBought = false;
                i = track;
            }
        }
        return overall_profit;
    }
}

I would appreciate any insights or suggestions on how to improve the current implementation to correctly solve the problem. Thank you!

Answer 1

You're looking for local minimums and maximums. I'm not going to write the code, but here's an outline of one algorithm.

Save the first price
Iterate through the array starting with the second element
    Is the current price less than the previous price
        Have you already bought stock
            Sell at the previous price
        else
            Save the current price
    else
        Have you already bought stock
            continue
        else
            Buy with the saved price.