Best Time to Buy and Sell Stock

Medium Arrays

Given daily prices, find the maximum profit from a single buy and a later sell. One pass, tracking the minimum price so far.

Sample input

[7, 1, 5, 3, 6, 4]

Sample output

Solution

def max_profit(prices):
    min_price = float("inf")
    best = 0
    for price in prices:
        min_price = min(min_price, price)
        best = max(best, price - min_price)
    return best

print(max_profit([7, 1, 5, 3, 6, 4]))

function maxProfit(prices) {
  let minPrice = Infinity, best = 0;
  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    best = Math.max(best, price - minPrice);
  }
  return best;
}

console.log(maxProfit([7, 1, 5, 3, 6, 4]));

public class Main {
    static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE, best = 0;
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            best = Math.max(best, price - minPrice);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
    }
}

fun maxProfit(prices: IntArray): Int {
    var minPrice = Int.MAX_VALUE
    var best = 0
    for (price in prices) {
        minPrice = minOf(minPrice, price)
        best = maxOf(best, price - minPrice)
    }
    return best
}

fun main() {
    println(maxProfit(intArrayOf(7, 1, 5, 3, 6, 4)))
}

func maxProfit(_ prices: [Int]) -> Int {
    var minPrice = Int.max, best = 0
    for price in prices {
        minPrice = min(minPrice, price)
        best = max(best, price - minPrice)
    }
    return best
}

print(maxProfit([7, 1, 5, 3, 6, 4]))

int maxProfit(List<int> prices) {
  int minPrice = 1 << 62, best = 0;
  for (final price in prices) {
    if (price < minPrice) minPrice = price;
    if (price - minPrice > best) best = price - minPrice;
  }
  return best;
}

void main() {
  print(maxProfit([7, 1, 5, 3, 6, 4]));
}

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

int maxProfit(const vector<int>& prices) {
    int minPrice = INT_MAX, best = 0;
    for (int price : prices) {
        minPrice = min(minPrice, price);
        best = max(best, price - minPrice);
    }
    return best;
}

int main() {
    cout << maxProfit({7, 1, 5, 3, 6, 4}) << endl;
    return 0;
}

#include <stdio.h>
#include <limits.h>

int maxProfit(int *prices, int n) {
    int minPrice = INT_MAX, best = 0;
    for (int i = 0; i < n; i++) {
        if (prices[i] < minPrice) minPrice = prices[i];
        if (prices[i] - minPrice > best) best = prices[i] - minPrice;
    }
    return best;
}

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    printf("%d\n", maxProfit(prices, 6));
    return 0;
}