20 Sep 2023, 4:40 PM
20 Sep 2023, 4:40 PM

12. Best Time to Buy And Sell Stock

#leetcode/121

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example:

Input: prices = [7, 2, 1, 5, 3, 6, 4]
Output: 5

Solution

Solution in C++ using two pointers

Let's understand this problem by an imagination. Imagine you have given a time machine, you can go to past to buy the stock of your choice when the price is very least. And again using that time machine went into future to sell the stock.
By doing that you have achieve maximum profit. From buying at very least price and selling at very higher price, you have become rich now!

Now let's just understand it with our given example. Remember one rule: You can only buy one time & sell one time.

  1. If we buy at 7 and sell at any time in the future, we'll face loss
  2. Now, I have seen a dip, I try to buy at 2 and see what's next...
  3. Oh no, another dip! Then, I try to buy at 1 and see what's next...
  4. I can sell at 5. My overall profit will be 5 - 1 = 4. We have achieved our maximum profit so far, put it aside.
  5. I could sell at 3... but then my profit would be 3 - 1 = 2 < 4. We don't like it.
  6. I can sell at 6. My overall profit will be 6 - 1 = 5. We have achieved our maximum profit so far, put it aside.
  7. I could sell at 4... but then my profit would be 4 - 1 = 3 < 5. We don't like it.
  8. We have achieved our maximum profit, we can return our answer.
int maxProfit(vector<int>& prices) {
	int maxSoFar = 0, n = prices.size();

	for(int low = 0, high = 1; high < n; high++) {
		if(prices[low] >= prices[high])
			low = high;
		else
			maxSoFar = max(maxSoFar, prices[high] - prices[low]);
	}
	return maxSoFar;
}

After we sell, you can see we don't care if the price goes down, we won't get greater profit.
As a result, we can move forward until we achieve greater profit or until the price goes reaally low (below the price we bought the stock).

int maxProfit(vector<int>& prices) {
	int n = prices.size(), low = 0, high = 1, maxSoFar = 0;
	
	while(high < n) {
		if(prices[low] >= prices[high]) {
			low = high;
			high++;
		}
		else {
			maxSoFar = max(maxSoFar, prices[high] - prices[low]);
			int currHigh = high;
			while (
					high < n &&
					prices[currHigh] >= prices[high] && 
					prices[high] > prices[low])
				high++;
		}
	}
	return maxSoFar;
}