Problem: Write a function that takes an array of stock prices and returns the best profit you could make from one purchase and one sale.

For example:

``````const prices = [10, 6, 3, 9, 11, 5];

maxProfit(prices);
// returns 8 (buying for \$3 and selling for \$11)
``````

## Brute Force Solution

Try every pair of times treating the earlier time as buy time and the later time as sell time, and see which one is higher.

``````// O(n^2) time
function maxProfit(prices) {
let maxProfit = 0;
for (let i=0; i < prices.length; i++) {
for (let j=0; j < prices.length; j++) {
let earlierTime = Math.min(i, j);
let laterTime = Math.max(i, j);

let earlierPrice = prices[earlierTime];
let laterPrice = prices[laterTime];

let potentialProfit = laterPrice - earlierPrice;

maxProfit = Math.max(maxProfit, potentialProfit);
}
}
return maxProfit;
}
``````

One problem: you can never have a negative profit!

## Better Solution

We have to compare every price so O(n) is the best we can do. Let’s take a greedy approach by keeping a running `maxProfit` until the end. So for every price check if:

• we can get a better profit by buying at `minPrice` and selling at `currentPrice`
• we can have a new `minPrice`

Initialize `maxProfit` as the first profit we could get, not `0`.

``````// O(n) time & O(1) space
function maxProfit(prices) {
let minPrice = prices;
let maxProfit = prices - prices;

for (let i = 1; i < prices.length; i++) {
let currentPrice = prices[i];
let potentialProfit = currentPrice - minPrice;
maxProfit = Math.max(maxProfit, potentialProfit);
minPrice = Math.min(minPrice, currentPrice);
}

return maxProfit;
}
``````

Want to improve your JavaScript? I have a list of recommended JavaScript books.