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;
}