Maximum Profit From Buying and Selling stock once

Given an array of numbers representing the stock prices of a company in chronological order, write a function that calculates the maximum profit you could have made from buying and selling that stock once. You must buy it before you can sell it.

Example:

Input:  arr={9,11,8,5,7,10}
Output: 5

Approach 1: Using Memory

C++

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

int maxProfit(vector<int> &prices)
{
    vector<pair<int, int>> v;
    int n = prices.size();
    if (n == 0)
        return 0;
    int max1 = prices[n - 1];
    for (int i = n - 1; i >= 0; i--)
    {
        max1 = max(max1, prices[i]);
        v.push_back({prices[i], max1});
    }
    int res = 0;
    for (int i = 0; i < n; i++)
    {

        if (v[i].second - v[i].first > res)
        {
            res = v[i].second - v[i].first;
        }
    }
    return res;
}

int main()

{
    vector<int> prices = {9, 11, 8, 5, 7, 10};

    cout << maxProfit(prices);

    return 0;
}

//Time Complexity: O(n)
//Space Complexity: O(n)

Approach 2: Memory Efficient

C++

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

int maxProfit(vector<int> &prices)
{
    int i = 1;
    if (prices.size() == 0)
        return 0;
    int buy, profit, sell, j;
    while (i < prices.size())
    {
        if (prices[i] < prices[i - 1])
            i++;
        else
        {
            j = i;
            break;
        }
    }
    if (i == prices.size())
        return 0;
    else
    {
        buy = prices[i - 1];
        sell = prices[j];
        profit = sell - buy;
        for (i = j + 1; i < prices.size(); i++)
        {
            if (prices[i] > sell)
            {
                sell = prices[i];
                if (sell - buy > profit)
                    profit = sell - buy;
            }
            else if (prices[i] < buy)
            {
                buy = prices[i];
                sell = prices[i];
            }
        }
    }
    return profit;
}
int main()

{
    vector<int> prices = {9, 11, 8, 5, 7, 10};

    cout << maxProfit(prices);

    return 0;
}

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