"Best Time to Buy and Sell Stock"系列的题都是非常有趣的。
1、Best Time to Buy and Sell Stock
Say you have an array for which theithelement is the price of a given stock on dayi.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
意思是说，我们已经知道一个数组prices[]，prices[i]表示的是第i天股票的价格。
只能买一次卖一次股票，问最大利润。
假设我们在第j天把股票卖了最赚，那么，买股票的日子必然在第j天或者第j天之前，并且买股票的日子必然是第j天或者第j天之前中股票价格最低的日子。
那么我们只需要从前往后扫一遍数组，更新最小值m，m表示的是第j天及以前的股票最低价格，然后更新最大利润即可。
class Solution {public:int maxProfit(vector<int> &prices) {if (prices.size() == 0) return 0;int ans = 0, s = prices.size(), m = prices[0];for (int i = 0; i < s; i++) {if (m > prices[i]) m = prices[i];if (prices[i] – m > ans) ans = prices[i] – m;}return ans;}};2、
Best Time to Buy and Sell Stock II
Say you have an array for which theithelement is the price of a given stock on dayi.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
题意与前面一样，，不同的是，我们可以多次买卖，但是我们买新的股票之前必须把手上的股票卖掉，也就是说，我们最多只能持有一个股票。
解法相当之简单，只要某一天的明天的股票价格比这一天高，我们就在这天买入并在明天卖出即可得到最大利润，比如3月25号的股票价格比3月26号低，那我25号就买，26号立刻卖。
为什么呢？
假设第i天的价格是pi，我们买入，第j天的价格是pj，我们卖出，而且第i天和第j天并不是连续的，那么：
首先pj必然大于等于pi，因为我们不做赔本生意；
1）中间有这么一天k，pi<pj<pk，那么pk-pi>pj-pi，也就是说我有更好地策略（在第k天卖出然后不买不卖直到第j天）可以赚到更多钱；
2）中间有这么一天k，pi<pk<pj，那么pj-pi=pj-pk+pk-pi，在第k天卖出至少不会亏；
3）中间有这么一天k，pk<pi<pj，那么pj-pk>pj-pi，也就是说我在第k天可以用更低的价钱买入然后在第j天卖出，可以赚更多的钱；
综上，如果买入卖出的两天不是连续的，那么赚到的钱不会比连续两天的多，甚至还会少，得证。
class Solution {public:int maxProfit(vector<int> &prices) {int ans = 0, s = prices.size();for (int i = 1; i < s; i++)if (prices[i] > prices[i – 1]) ans += prices[i] – prices[i – 1];return ans;}};3、
Best Time to Buy and Sell Stock III
Say you have an array for which theithelement is the price of a given stock on dayi.
Design an algorithm to find the maximum profit. You may complete at mosttwotransactions.
Note:You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
只能买两次卖两次。
一开始觉得这题非dp莫属了，结果在Discuss看到了这种解法：
https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1
就像看到了黑魔法一般。
具体思路还不是很懂，下面的代码参考了上述链接中的代码，其中的值的意思是：
h1:买到手头上第一个股票的最大利润；
h2:买到手头上第二个股票的最大利润（也就是说之前手头上已经有了一个股票）；
r1:卖掉第一个股票的最大利润；
r2:卖掉第二个股票的最大利润；
还需要留意到的是，r2依赖于h2，h2依赖于r1，r1依赖于h1，所以循环中的四行代码之所以这样排，是为了当前循环中的变量依赖于上一次循环；
class Solution {public:int maxProfit(vector<int> &prices) {if (prices.size() == 0) return 0;int h1 = -prices[0], h2 = -prices[0], r1 = 0, r2 = 0, s = prices.size();for (int i = 0; i < s; i++) {if (h2 + prices[i] > r2) r2 = h2 + prices[i];if (r1 – prices[i] > h2) h2 = r1 – prices[i];if (h1 + prices[i] > r1) r1 = h1 + prices[i];if (-prices[i] > h1) h1 = -prices[i];}return r2;}};4、
Best Time to Buy and Sell Stock IV
Say you have an array for which theithelement is the price of a given stock on dayi.
Design an algorithm to find the maximum profit. You may complete at mostktransactions.
Note:You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Credits:Special thanks to@Freezenfor adding this problem and creating all test cases.
最多进行k次交易。
也就是买卖总数是2k次。那么，当k≥n/2的时候，每个股票都可以被买或者卖，也就回到了第二题的情况；否则是第三题情况。
class Solution {public:int maxProfit(int k, vector<int> &prices) {if (k >= prices.size() / 2) return maxProfit(prices);if (prices.size() == 0) return 0;int * h = new int[k + 1], *r = new int[k + 1], s = prices.size();for (int i = 1; i <= k; i++) h[i] = -prices[0], r[i] = 0;h[0] = r[0] = 0;for (int i = 0; i < s; i++)for (int j = k; j > 0; j–) {if (h[j] + prices[i] > r[j]) r[j] = h[j] + prices[i];if (r[j – 1] – prices[i] > h[j]) h[j] = r[j – 1] – prices[i];}s = r[k];delete[]h, delete[]r;return s;}int maxProfit(vector<int> &prices) {int ans = 0, s = prices.size();for (int i = 1; i < s; i++)if (prices[i] > prices[i – 1]) ans += prices[i] – prices[i – 1];return ans;}};
正确的寒暄必须在短短一句话中明显地表露出你对他的关怀。
