122. Best Time to Buy and Sell Stock II

Given an integer array prices , prices[i] is the price of a given stock on the ith day. If can hold only a single share and can buy and/or sell the stock on same day.

Find the maximum profit possible.

---

Intuition

• To achieve the max profit we need to buy on low day and sell on high day.

• Since we can buy/sell multiple times we perform trades where $price[i] < price[i+1]$

• If $price[i-1] < price[i] < price[i+1]$ we hold on day $i$ as we can sell on day $i+1$.

Approach

• Iterate over the array while maintaining buy price.

• If we encounter day where price next day will be higher we hold

• If the price the next day is less, sell now and buy tomorrow

Complexity

• Time complexity : $\text{O}(1)$

  • we iterate over the array only once

• Space complexity : $\text{O}(1)$

  • no extra space is needed

Code

public int maxProfit(int[] prices) {
	int maxProfit= 0, buyPrice = -1;


	for (int i = 0; i < prices.length -1; i++ ) {
		if(prices[i] <= prices[i+1]) {
			// hold if bought earlier
			// if we haven't baought earlier buy now
			if(buyPrice == -1) buyPrice = prices[i];
		} else {
			if(buyPrice != -1) {
				maxProfit += prices[i] - buyPrice;
				
				// to check if we can buy on same day for profit
				buyPrice = -1;
				i--;	
			}	
		}
	}
	
	// we bought at some point but couldn't sell
	// as everyday price increased so sell on the last day

	if(buyPrice != -1) {
		maxProfit += prices[prices.length-1] - buyPrice;
	}
	
	return maxProfit;
}