DEV Community

Daily Challenge #228 - Best Profit in Single Sale

dev.to staff on April 17, 2020

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 ...

Read full post

Akhil • Apr 17 '20 • 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 • Apr 17 '20

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?

Akhil • Apr 18 '20 • Edited

Thanks for pointing out, it's a typo. My bad. I have updated the code.

Craig McIlwrath • Apr 17 '20

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 • Apr 18 '20

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

Craig McIlwrath • Apr 18 '20

Oh, I misunderstood the challenge. Didn't notice that order requirement.

Andreas Jakof • Apr 18 '20

Don‘t worry... just wanted to point out to you, that you are not done yet. 😬
Keep at it

Vidit Sarkar • Apr 17 '20

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[1] - prices[0];

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

    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 • Apr 17 '20

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

Vidit Sarkar • Apr 17 '20

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 • Apr 17 '20

Here is a short Python recursive solution,

def max_profit(prices: list) -> int:
    if(len(prices) == 2):
        return prices[1] - prices[0]
    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 • Apr 17 '20

Elm

import List.Extra


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