Given an array prices[] of non-negative integers, representing the prices of the stocks on different days, find the maximum profit possible by buying and selling the stocks on different days when at most one transaction is allowed. Here one transaction means 1 buy + 1 Sell. If it is not possible to make a profit then return 0.

Note: Stock must be bought before being sold.

Examples:

Input: prices[] = [7, 10, 1, 3, 6, 9, 2]
Output: 8
Explanation: Buy for price 1 and sell for price 9.
Input: prices[] = [7, 6, 4, 3, 1]
Output: 0
Explanation: Since the array is sorted in decreasing order, 0 profit can be made without making any transaction.

Input: prices[] = [1, 3, 6, 9, 11]
Output: 10
Explanation: Since the array is sorted in increasing order, we can make maximum profit by buying at price[0] and selling at price[n-1]

Try it on GfG Practice

Table of Content

[Naive Approach] By exploring all possible pairs - O(n^2) Time and O(1) Space
[Expected Approach] One Traversal Solution - O(n) Time and O(1) Space

[Naive Approach] By exploring all possible pairs - O(n^2) Time and O(1) Space

The idea is to use two nested loops to explore all the possible ways to buy and sell stock. The outer loop decides the day to buy the stock and the inner loop decides the day to sell the stock. The maximum difference between the selling price and buying price between every pair of days will be our answer.

C++

#include <iostream>
#include <vector>
using namespace std;

int maxProfit(vector<int> &prices) {  
    int n = prices.size();
    int res = 0;
  
    // Explore all possible ways to buy and sell stock
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
			res = max(res, prices[j] - prices[i]);
        }
    }
    return res;
}

int main() {
    vector<int> prices = {7, 10, 1, 3, 6, 9, 2};
    cout << maxProfit(prices) << endl;
    return 0;
}

#include <stdio.h>

int maxProfit(int prices[], int n) {
    int res = 0;

    // Explore all possible ways to buy and sell stock
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (prices[j] - prices[i] > res) {
                res = prices[j] - prices[i];
            }
        }
    }
    return res;
}

int main() {
    int prices[] = {7, 10, 1, 3, 6, 9, 2};
    int n = sizeof(prices) / sizeof(prices[0]);
    printf("%d\n", maxProfit(prices, n));
    return 0;
}

Java

class GfG {

    static int maxProfit(int[] prices) {
        int n = prices.length;
        int res = 0;

        // Explore all possible ways to buy and sell stock
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                res = Math.max(res, prices[j] - prices[i]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] prices = {7, 10, 1, 3, 6, 9, 2};
        System.out.println(maxProfit(prices));
    }
}

Python

def max_profit(prices):
    n = len(prices)
    res = 0

    # Explore all possible ways to buy and sell stock
    for i in range(n - 1):
        for j in range(i + 1, n):
            res = max(res, prices[j] - prices[i])
    
    return res

if __name__ == "__main__":
    prices = [7, 10, 1, 3, 6, 9, 2]
    print(max_profit(prices))

using System;
using System.Collections.Generic;

class GfG {
    static int maxProfit(int[] prices) {
        int n = prices.Length;
        int res = 0;

        // Explore all possible ways to buy and sell stock
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                res = Math.Max(res, prices[j] - prices[i]);
            }
        }
        return res;
    }

    static void Main() {
        int[] prices = { 7, 10, 1, 3, 6, 9, 2 };
        Console.WriteLine(maxProfit(prices));
    }
}

JavaScript

function maxProfit(prices) {
    let n = prices.length;
    let res = 0;

    // Explore all possible ways to buy and sell stock
    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            res = Math.max(res, prices[j] - prices[i]);
        }
    }
    return res;
}

//Driver Code
let prices = [7, 10, 1, 3, 6, 9, 2];
console.log(maxProfit(prices));

Output

[Expected Approach] One Traversal Solution - O(n) Time and O(1) Space

In order to maximize the profit, we need to minimize the cost price and maximize the selling price. So at every step, we keep track of the minimum buy price of stock encountered so far. For every price, we subtract with the minimum so far and if we get more profit than the current result, we update the result.

C++

#include <iostream>
#include <vector>
using namespace std;

int maxProfit(vector<int> &prices) {
  
    int minSoFar = prices[0], res = 0;
  
    for (int i = 1; i < prices.size(); i++) {

        // Update the minimum value seen so far
        minSoFar = min(minSoFar, prices[i]);
       
        // Update result if we get more profit                
        res = max(res, prices[i] - minSoFar);
    }
    return res;
}

int main() {
    vector<int> prices = {7, 10, 1, 3, 6, 9, 2};
    cout << maxProfit(prices) << endl;
    return 0;
}

#include <stdio.h>

int maxProfit(int prices[], int size) {
    int minSoFar = prices[0];
    int res = 0;
  
    for (int i = 1; i < size; i++) {
      
        // Update the minimum value seen so far  
        if (prices[i] < minSoFar) {
            minSoFar = prices[i];
        }
       
        // Update result if we get more profit                
        if (prices[i] - minSoFar > res)
            res = prices[i] - minSoFar;
    }
    return res;
}

int main() {
    int prices[] = {7, 10, 1, 3, 6, 9, 2};
    int size = sizeof(prices) / sizeof(prices[0]);
    printf("%d\n", maxProfit(prices, size));
    return 0;
}