Problem 6.8 - proposed alternative solution with lower space complexity

#1

Version 1.5.1 shows the following solution which is indicated to have O(n) time complexity and O(n) additional space complexity:

int BuyAndSellStockTwice() {
    double max_total_profit = 0;
    vector<double> first_buy_sell_profits(prices.size(), 0);
    double min_price_so_far = numeric_limits<double>::max();
    //for each day record max profit if sell made that day
    for (size_t i = 0; i < prices.size(); ++i) {
            min_price_so_far = min(min_price_so_far, prices[i]);
            max_total_profit = max(max_total_profit, prices[i] - min_price_so_far);
            first_buy_sell_profits[i] = max_total_profit;
    }
    //for each day find max profit if second buy made that day
    double max_price_so_far = numeric_limits<double>::min();
    for (size_t i = prices.size() - 1; i > 0; --i) {
        max_price_so_far = max(max_price_so_far, prices[i]);
        max_total_profit = max(max_total_profit, max_price_so_far - prices[i] + first_buy_sell_profits[i - 1]);
    }
    return max_total_profit;
}

I propose the following alternative, also with O(n) time complexity and with only O(1) additional space complexity (an improvement to the O(n) space complexity of the above current solution):

double BuyAndSellStockTwice(const vector<double>& prices) {
    double max1 = 0, max2 = 0;
    double min_price_so_far = numeric_limits<double>::max();
    for(auto const& cur : prices) {
        if (min_price_so_far > cur) min_price_so_far = cur;
        double profit = cur - min_price_so_far;
        if (profit > max2) {
            if (profit > max1) {
                max2 = max1;
                max1 = profit;
            }
            else {
                max2 = profit;
            }
        }
    }
    double max_total_profit = max1 + max2;
    return max_total_profit;
}

Cheers.

0 Likes
#2

Prior proposal withdrawn! It solves a problem, but not the one that the authors have posed in Problem 6.8.

Let’s try this proposed solution instead, which is a little more complicated because it adds logic to ensure that the two best buy/sell pairs do not have matching buy days, but still has lower space complexity than before:

double BuyAndSellStockTwice(const vector<double>& prices) {
    double max1 = 0, max2 = 0, min_price_so_far = numeric_limits<double>::max();
    size_t day_cur = 0, buy_day_min_price_so_far = 0, buy_day_max1 = 0;
    for(auto const& cur : prices) {
        if (min_price_so_far >= cur) {
            min_price_so_far = cur;
            buy_day_min_price_so_far = day_cur;
        }
        double profit = cur - min_price_so_far;
        if (profit > max2) {
            if (profit > max1) {
                if (buy_day_min_price_so_far > buy_day_max1) { // else, max1 has been superseded for same buy day, so do not preserve
                    max2 = max1;
                }
                max1 = profit;
                buy_day_max1 = buy_day_min_price_so_far;
            }
            else  {
                max2 = profit;
            }
        }
        ++day_cur;
    }
    double max_total_profit = max1 + max2;
    return max_total_profit;
}
0 Likes
#3

Hey,

Very good solution indeed. I have to thank for your contribution to this problem as it shall solve the variant of this problem. BTW, if you take a look at the solution of solving similar problem with buy and sell k times, you will notice the similarity of these two solutions where both use O(1) space and O(n) time. Please let me know what you think, and thank again for your awesome idea here.

0 Likes