DEV Community

loading...

Discussion on: Daily Challenge #228 - Best Profit in Single Sale

Collapse
vidit1999 profile image
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[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;
}
Collapse
blazephoenix profile image
Tanmay Naik

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

Collapse
vidit1999 profile image
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.