## Friday, September 11, 2015

### LeetCode OJ - Best Time to Buy and Sell Stock

Problem:

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.

 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"

#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

{
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;
}
};
};

}