Best Time to Buy and Sell Stock II | Leetcode

Say you have an array for which the i^th 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 (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

---

Solution: Iterate through the prices array from beginning to end. Find the current lowest price, which is defined as the price which is lower than its next price. Then find the current highest price, which is defined as the price which is higher than its next price. Capture the profit by subtracting the current lowest price from the current highest price. Repeat until we reach the end of the loop.

The boundary cases are very tricky, so have to be extra careful.

public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        int last = prices.length - 1;
        int i = 0;
        do {
            // Find the current lowest point.
            while (i < last && prices[i] >= prices[i + 1]) i++;
            if (i >= last) break;
            int lo = prices[i++];
            
            // Find the current highest point.
            while (i <= last && prices[i - 1] <= prices[i]) i++;
            int hi = prices[i - 1];
            
            // Capture current profit if any.
            if (hi > lo) profit += hi - lo;
        } while (i < last);
        return profit;
    }
}