Home | Projects | Notes > Problem Solving > EPI - 6.7. Buy and Sell a Stock Once

EPI - 6.7. Buy and Sell a Stock Once

Solutions in C++

Solution 1

The key is to compute the maximum profit by computing the difference of the current entry with the minimum value seen so far as we iterate through the array.

Complexity Analysis:

• $T=O(n)$$T = O(n)$, where $n$$n$ is the length of the array

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
15
1
#include <vector>
2

3
double BuyAndSellStockOnce(const vector<double>& prices)
4
{
5
    double min_price_so_far = prices.at(0), max_profit = 0;
6
    
7
    for (auto price : prices)
8
    {
9
        double max_profit_sell_today = max(price - min_price_so_far, max_profit);
10
        max_profit = max(max_profit, max_profit_sell_today);
11
        min_price_so_far = min(min_price_so_far, price);
12
    }
13

14
    return max_profit;
15
}

Solutions in C

Solution 1

The key is to compute the maximum profit by computing the difference of the current entry with the minimum value seen so far as we iterate through the array.

Complexity Analysis:

• $T=O(n)$$T = O(n)$, where $n$$n$ is the length of the array

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
19
1
double BuyAndSellStockOnce(const double *prices, int size)
2
{
3
    double min_price_so_far = prices[0], max_profit = 0;
4
    double max_profit_sell_today = 0;
5

6
    for (int i = 0; i < size; i++)
7
    {
8
        max_profit_sell_today = (prices[i] - min_price_so_far) > max_profit ? 
9
            (prices[i] - min_price_so_far) : max_profit;
10

11
        max_profit = max_profit > max_profit_sell_today ? 
12
            max_profit : max_profit_sell_today;
13

14
        min_price_so_far = min_price_so_far > prices[i] ? 
15
            prices[i] : min_price_so_far;
16
    }
17

18
    return max_profit;
19
}