Stock Buy and Sell - 1

Problem Link -Stock buy and sell

Problem Statement
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 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation:Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Intuition

• To get maximum profit, we need to select a day that has minimum price for buying and another day which has a maximum price for selling.
• while selecting, we also need to make sure that we must buy the stock before selling it.

Approach

• Try selling stock at every index and find the profit that can be obtained. At last we will return maximum among all these profits.
• To get maximum profit by selling stock at every index in a single traversal we will keep track of lowest possible buying price that we have bought so far, and if you find a lower price than your current buy price, you update it, because this could potentially lead to a higher profit later.
• For each price, you're essentially asking, "If I sell at this price, what profit would I make with the current lowest buy price?" You check all potential profits at every index and keep track of the maximum profit seen so far.

Solution

• We will start from the 0th index by buying the stock at that index, because to make a transaction at any index first we need to buy it.
• Store it in a variable called buy which stores the miniumum price that we have seen so far buy=prices[0]
• Declare a maxi variable that stores the maximum profit seen so far maxi=0
• To obtain the maximum profit, we will start checking for price to sell the stock that we have bought so far, by iterating through the prices list starting from 1st index(because buying and selling on same day on 0th index results in 0 profit)
• we will try selling the stock bought at every index, and at each iteration i we will check whether is it possible to sell the stock at the current index by checking prices[i]>buy. If yes then sell the stock and update maxi variable maxi=max(maxi,prices[i]-buy). if not then this will be the minimum price that we have seen so far, so update buy variable. buy=prices[i]

Cpp Code

int maxProfit(vector<int>& prices) {
    if (prices.empty()) {
        return 0;
    }
   int buy = prices[0]; // Set initial buying price to 1st day's price
    int maxi = 0;   // Set initial maximum profit to 0
    for (int i = 1; i < prices.size(); ++i) {
        if (prices[i] > buy) {
            maxi = max(maxi, prices[i] - buy);
        }
        else {
            buy = prices[i];
        }
    }
    return maxi;
}