Problem Statement

Given an array prices[] where prices[i] represents the price of a stock on the ith day, we need to find the maximum profit that can be obtained by making a single buy-sell transaction.

In other words, we need to find the maximum difference prices[j] - prices[i] where i < j.

Examples:

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

Example 2:

Input: prices[] = {7, 6, 4, 3, 1}
Output: 0

Explanation: In this case, no transaction is done, i.e., max profit = 0

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Algorithm:

1. Iterate through each day i from 0 to n - 1, where n is the size of the input array.
2. For each day i, iterate through each subsequent day j from i + 1 to n - 1.
3. Calculate the profit prices[j] - profit[i] for each pair of days (i, j).
4. Keep track of the maximum profit found so far.
5. Finally, return the maximum profit obtained after iterating through all possible pairs.

Code:

#include<bits/stdc++.h>
using namespace std;

int maxProfit(vector<int> &arr) {
    int maxPro = 0;
    int n = arr.size();

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[i]) {
            maxPro = max(arr[j] - arr[i], maxPro);
            }
        }
        }

    return maxPro;
}

int main() {
    vector<int> arr = {7,1,5,3,6,4};
    int maxPro = maxProfit(arr);
    cout << "Max profit is: " << maxPro << endl;
}

Complexity Analysis:

• Time Complexity: O(N ^ 2)
• Space Complexity: O(1)

2️⃣ Optimal Approach

Intuition:

The problem can be reduced to finding the minimum price to buy the stock and the maximum price to sell the stock afterward. We need to keep track of the minimum price we’ve encountered so far and calculate the profit we would get by selling the stock on the current day. Our goal is to maximize this profit.

By traversing the array linearly, we maintain a variable to store the minimum price encountered so far. As we move forward in the array, we compare each element with this minimum. If the current element is greater than the minimum, we update the maximum profit if the difference between the current element and the minimum is greater than the previously recorded maximum profit. Otherwise, we update the minimum price encountered.

Algorithm:

1. Initialize two variables:
   1. minPrice: To keep track of the lowest stock price seen so far.
   2. maxProfit: To store the maximum profit possible.
2. Traverse through the prices array:
   1. For each day, check if the current price is less than minPrice. If so, update minPrice.
   2. Calculate the potential profit if we sell the stock on the current day (current price - minPrice).
   3. Update maxProfit if the calculated profit is greater than the previous maximum profit.
3. At the end of the traversal, maxProfit will contain the maximum profit that can be made by one buy-sell transaction.

Dry Run:

Initialization:

         +-----+-----+-----+-----+-----+-----+
prices = |  7  |  1  |  5  |  3  |  6  |  4  |
         +-----+-----+-----+-----+-----+-----+

minPrice = 7
maxProfit = 0

Iteration 1:

         +-----+-----+-----+-----+-----+-----+
prices = |  7  |  1  |  5  |  3  |  6  |  4  |
         +-----+-----+-----+-----+-----+-----+
                  ^
                  |
                  i

minPrice = 7
maxProfit = 0

    prices[i] < minPrice
            1 < 7
            True,
            Update minPrice to prices[i]
            minPrice = 1

Iteration 2:

         +-----+-----+-----+-----+-----+-----+
prices = |  7  |  1  |  5  |  3  |  6  |  4  |
         +-----+-----+-----+-----+-----+-----+
                        ^
                        |
                        i

minPrice = 1
maxProfit = 0

    prices[i] < minPrice
            5 < 1
            False
    Else Calculate maxProfit if we sell today
         maxProfit = max(prices[i] - minPrice, maxProfit)
                   = max(5 - 1, 0)
                   = max(4, 0)
                   = 4

Iteration 3:

         +-----+-----+-----+-----+-----+-----+
prices = |  7  |  1  |  5  |  3  |  6  |  4  |
         +-----+-----+-----+-----+-----+-----+
                              ^
                              |
                              i

minPrice = 1
maxProfit = 4

    prices[i] < minPrice
            3 < 1
            False
    Else Calculate maxProfit if we sell today
         maxProfit = max(prices[i] - minPrice, maxProfit)
                   = max(3 - 1, 4)
                   = max(2, 4)
                   = 4

Iteration 4:

         +-----+-----+-----+-----+-----+-----+
prices = |  7  |  1  |  5  |  3  |  6  |  4  |
         +-----+-----+-----+-----+-----+-----+
                                    ^
                                    |
                                    i

minPrice = 1
maxProfit = 4

    prices[i] < minPrice
            6 < 1
            False
    Else Calculate maxProfit if we sell today
         maxProfit = max(prices[i] - minPrice, maxProfit)
                   = max(6 - 1, 4)
                   = max(5, 4)
                   = 5

Iteration 5:

         +-----+-----+-----+-----+-----+-----+
prices = |  7  |  1  |  5  |  3  |  6  |  4  |
         +-----+-----+-----+-----+-----+-----+
                                          ^
                                          |
                                          i

minPrice = 1
maxProfit = 5

    prices[i] < minPrice
            4 < 1
            False
    Else Calculate maxProfit if we sell today
         maxProfit = max(prices[i] - minPrice, maxProfit)
                   = max(4 - 1, 5)
                   = max(3, 5)
                   = 5

Iteration 6 (Loop Termination):

         +-----+-----+-----+-----+-----+-----+
prices = |  7  |  1  |  5  |  3  |  6  |  4  |
         +-----+-----+-----+-----+-----+-----+
                                                 ^
                                                 |
                                                 i

minPrice = 1
maxProfit = 5

   Since i has exceeds the array bounds,
   the loop will terminate here. The answer
   is in maxProfit variable.

Code:

#include <iostream>
#include <vector>
#include <algorithm> // for max, min
using namespace std;

int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;

    int minPrice = prices[0]; // Initially set to the first day's price
    int maxProfit = 0;        // Initially, no profit is made

    for (int i = 1; i < prices.size(); i++) {
        // Update the minimum price if a lower price is found
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            // Calculate profit by selling on day i
            int profit = prices[i] - minPrice;
            // Update maxProfit if this profit is greater
            maxProfit = max(maxProfit, profit);
        }
    }

    return maxProfit;
}

int main() {
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    cout << "Maximum Profit: " << maxProfit(prices) << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(1)