# Daily Challenge #228 - Best Profit in Single Sale

You're a buyer/seller and your business is at stake. You need to make profit... Or at least, you need to lose the least amount of money! Knowing a list of prices for buy/sell operations, you need to pick two of them. Buy/sell market is evolving across time and the list represent this evolution. First, you need to buy one item, then sell it later. Find the best profit you can do.

Input:
A list of prices (integers), of length 2 or more.

Output:
The result of the best buy/sell operation, as an integer.

Example:
Given an array of prices [3, 10, 8, 4], the best profit you could make would be 7 because you buy at 3 first, then sell at 10.

Tests:
max_profit([10, 7, 5, 8, 11, 9])
max_profit([3, 4])
max_profit([9, 9])
max_profit([10, 7, 5, 4, 1])

Good luck!

This challenge comes from wontonst on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions! Simple Haskell solution. Uses the property that the maximum difference of two items in a list will be the difference between the maximum and minimum elements.

``````maxProfit :: (Ord a, Num a) => [a] -> a
maxProfit [] = 0
maxProfit xs = maximum xs - minimum xs
`````` Andreas Jakof

If max comes before min, then this solution would show a wrong result. Akhil • Edited

O(n) time and O(1) space: Kadane's algorithm

``````var maxProfit = function(prices) {
let maxCurr = 0;
let maxSale = 0;
for(let i=1;i<prices.length;i++){
maxCurr = Math.max(0,maxCurr += prices[i]-prices[i-1]);
maxSale = Math.max(maxCurr,maxSale);
}
return maxSale;
};

console.log(maxProfit([5,6,7,1,2,5,9]));
`````` Amin

Nice one, but there are some things that bother me in the code.

You could have replaced the `var` by a `let` or a `const` in the first line since you are using `let` later.

You can increase the speed execution of your algorithm by caching the length of the `prices` variables, which is not changing over the course of your iterations.

Your variable `maxCurr` lacks a variable declaration keyword: either `let` or `const`.

Also, you are using the `maxCurr` variable before even declaring it. That does not make sense.

I tried to run it but it threw some exceptions, did you run it on your local machine? Vidit Sarkar

C++ solution

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

// returns the maximum profit (or minimum loss) user can make
// by buying and selling one item
int max_profit(vector<int> prices){
// stores the maximum profit made so far
int maxProfitSoFar = prices - prices;

// stores the minimum price seen so far
int minPriceSoFar = min(prices, prices);

for(int i = 2; i < prices.size(); i++){
// maximum profit will be the maximum of
// (current price - minimum price seen before) and maximum profit so far
maxProfitSoFar = max(prices[i] - minPriceSoFar, maxProfitSoFar);

// minimum price will be minimum of
// current price and minimum price seen before
minPriceSoFar = min(prices[i], minPriceSoFar);
}

return maxProfitSoFar;
}

// main function
int main(){
cout << max_profit({3, 10, 8, 4}) << "\n"; // output -> 7
cout << max_profit({10, 7, 5, 8, 11, 9}) << "\n"; // output -> 6
cout << max_profit({3, 4}) << "\n"; // output -> 1
cout << max_profit({9, 9}) << "\n"; // output -> 0
cout << max_profit({10, 7, 5, 4, 1}) << "\n"; // output -> -1
return 0;
}
`````` Tanmay Naik

How is the last output -1? Shouldn't it be 9? Vidit Sarkar

Here I represented the loss with negative number.

For the last case the vector is sorted in descending order. So there is no way user will make any profit. The minimum loss is 1 (i.e. buy the item at price 5 and sell it at price 4).

Remember you have to buy the item first and then sell it. Vidit Sarkar

Here is a short Python recursive solution,

``````def max_profit(prices: list) -> int:
if(len(prices) == 2):
return prices - prices
return max(prices[-1] - min(prices[:-1]), max_profit(prices[:-1]))
``````

Test Cases,

``````print(max_profit([3, 10, 8, 4])) # output -> 7
print(max_profit([10, 7, 5, 8, 11, 9])) # output -> 6
print(max_profit([3, 4])) # output -> 1
print(max_profit([9, 9])) # output -> 0
print(max_profit([10, 7, 5, 4, 1])) # output -> -1
`````` Amin

Elm

``````import List.Extra

maxProfit : List Int -> Int
maxProfit =
List.Extra.uniquePairs
>> List.map (\(a, b) -> b - a)
>> List.maximum
>> Maybe.withDefault 0
``````