Best Time to Buy and Sell Stock I II III IV （第四周 動態規劃）

Best Time to Buy and Sell Stock I

Say you have an array for which the ith element is the price of a given stock on day i.
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.

Example:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

算法思路

使用動態規劃，從左到右遍歷一遍數組，記錄一下當前出現的最低的股票價格，并且與當前股票價格作對比，如果當前的更低，就更新最低股票價格，并且用當前股票價格減去最低股票價格得到可能的最大收益，并且與全局最大收益對比，取最大。

算法代碼

class Solution { public:int maxProfit(vector<int>& prices) {int len = prices.size();if(len == 0)return 0;int res = 0;int cur = prices[0];for(int i = 0; i < prices.size(); i++){cur = min(cur,prices[i]);res = max(res,prices[i] - cur);}return res;} };

時空復雜度

時間復雜度：O（n）
空間復雜度：O（1）

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.
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).

Subscribe to see which companies asked this question.

算法思路

使用貪心算法，從左到右遍歷數組，只要當前股票價格大于前一天的價格，就會有收益，當前的差值就是今天的收益，我們累加這些差值，就可以得到最終的收益。

算法代碼

class Solution { public:int maxProfit(vector<int>& prices) {int len = prices.size();if(len == 0)return 0;int res = 0;for(int i = 1; i < len; i++){int diff = prices[i] - prices[i - 1];if(diff > 0)res += diff;}return res;} };

時空復雜度

時間復雜度：O（n）
空間復雜度：O（1）

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Subscribe to see which companies asked this question.

算法思路

使用動態規劃，也使用到了二分的思想。以第i天為一個分解析，我們要維護兩個數組pre與post，pre[i]與post[i]分別表示第i天之前進行一次交易的最大收益和第i天之后進行一次交易的最大收益。最后再遍歷一遍數組，得到max{pre[i] + post[i]} 就是最大的收益。至于pre和post的值的求法和Best Time to Buy and Sell Stock I是一樣的，都是用動態規劃的方法在線性時間內求得。要注意的是，pre是從前往后遍歷數組，而post是從后往前遍歷數組。

算法代碼

class Solution { public:int maxProfit(vector<int>& prices) {int len = prices.size();if(len == 0)return 0;int res = 0,preres[99999],postres[99999];int tmp;for(int i = 0 ; i < len; i++)postres[i] = 0, preres[i] = 0;tmp = prices[0];int cur = 0;for(int i = 1; i < len; i++){tmp = min(tmp,prices[i]);preres[i] = max(cur,prices[i] - tmp);cur = max(preres[i],cur);}tmp = prices[len - 1];cur = 0;for(int i = len - 2; i >= 0; i--){tmp = max(tmp,prices[i]);postres[i] = max(cur,tmp - prices[i]);cur = max(postres[i],cur);}for(int i = 0; i < len; i++)res = max(res,postres[i] + preres[i]);return res;} };

時空復雜度

時間復雜度：O（n）
空間復雜度：O（n）

Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

算法思路

用特殊的動態規劃。我們先定義兩個矩陣local與global，local[i][j]為在到達第i天時最多可進行j次交易并且最后一次交易在最后一天賣出的最大利潤，此為局部最優。global[i][j]為在到達第i天時最多可進行j次交易的最大利潤，此為全局最優。然后動態規劃的轉移公式為：

local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
global[i][j] = max(local[i][j], global[i - 1][j])，

其中局部最優值是比較前一天并少交易一次的全局最優加上大于0的差值，和前一天的局部最優加上差值后相比，兩者之中取較大值，而全局最優比較局部最優和前一天的全局最優。要注意的是，如果k的值遠大于prices的天數，該dp算法會很慢，應該直接使用Best Time to Buy and Sell Stock II 的貪心算法求解。

算法代碼

class Solution { public:int maxProfit(int k, vector<int> &prices) {if (prices.empty()) return 0;if (k >= prices.size()) return solveMaxProfit(prices);int g[k + 1] = {0};int l[k + 1] = {0};for (int i = 0; i < prices.size() - 1; ++i) {int diff = prices[i + 1] - prices[i];for (int j = k; j >= 1; --j) {l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);g[j] = max(g[j], l[j]);}}return g[k];}int solveMaxProfit(vector<int> &prices) {int res = 0;for (int i = 1; i < prices.size(); ++i) {if (prices[i] - prices[i - 1] > 0) {res += prices[i] - prices[i - 1];}}return res;} };

時空復雜度

時間復雜度：O（n）
空間復雜度：O（k）

總結

以上是生活随笔為你收集整理的Best Time to Buy and Sell Stock I II III IV （第四周 动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。