online advertising

Friday, September 11, 2015

LeetCode OJ - Best Time to Buy and Sell Stock

Problem:

Please find the problem here.

Solution:

Brute force would be quadratic. Consider this sequence of prices

10, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5

If we where considering to buy at time 0, then we know it is best to sell it at time = 1 by going through the whole list.

But when we consider buying at time 1, do we still need to scan the whole list? Probably not, we already knew only time 1 is the best possible time to sell, and that only require the price to be highest, it has nothing to do with the buying price.

Therefore it make sense the think about the selling price 'envelop' like this

price:10, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5
best selling price:11, 11, 10, 9, 8, 7, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5

The best selling price envelop means what would be the best price to sell if I hold some stock right now.

Similarly, we can also think about the best buying price envelop,

price:10, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5
best buying price:10, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1

The best buying price means the best price I could have if I want to hold some stock right now.

With the two envelops, now the algorithm is easy, just pick the largest element from the difference.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

#include "LEET_BEST_TIME_TO_BUY_AND_SELL_STOCK.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_BEST_TIME_TO_BUY_AND_SELL_STOCK
{
    class Solution
    {
    public:
        int maxProfit(vector<int>& prices)
        {
            int num_days = prices.size();

            if (num_days < 2)
            {
                return 0;
            }

            vector<int> min_cost;
            vector<int> max_sold;
            min_cost.resize(num_days);
            max_sold.resize(num_days);

            min_cost[0] = prices[0];
            for (int i = 1; i < num_days; i++)
            {
                min_cost[i] = min(min_cost[i - 1], prices[i]);
            }

            max_sold[num_days - 1] = prices[num_days - 1];
            for (int i = num_days - 2; i >= 0; i--)
            {
                max_sold[i] = max(max_sold[i + 1], prices[i]);
            }

            int max_profit = 0;
            for (int i = 0; i < num_days; i++)
            {
                max_profit = max(max_profit, max_sold[i] - min_cost[i]);
            }

            return max_profit;
        }
    };
};

using namespace _LEET_BEST_TIME_TO_BUY_AND_SELL_STOCK;

int LEET_BEST_TIME_TO_BUY_AND_SELL_STOCK()
{
    Solution s;
    int case1[] = { 10, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5 };
    cout << s.maxProfit(vector<int>(case1, case1 + _countof(case1))) << endl;
    return 0;
}

No comments :

Post a Comment