121.買賣股票的最佳時機
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多隻允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能擷取的最大利潤。
注意你不能在買入股票前賣出股票。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。 122.買賣股票的最佳時機II
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個算法來計算你所能擷取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
随後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之後再将它們賣出。
因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。 123.買賣股票的最佳時機III
給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。
設計一個算法來計算你所能擷取的最大利潤。你最多可以完成 兩筆 交易。
注意: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [3,3,5,0,0,3,1,4]
輸出: 6
解釋: 在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。
随後，在第 7 天（股票價格 = 1）的時候買入，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3 。 示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之後再将它們賣出。
因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這個情況下, 沒有交易完成, 是以最大利潤為 0。 解題思路：
這三題都是類似的思想，第一題的掌握程度直接決定，二，三題是否能較快得解出來。
121中，有兩種解法。
121-1：求解第i天買入股票,價格為val[i]，能賺取的最大利潤m[i]。[i,end)區間的最大值為max,于是m[i]=max-val[i]。最終再求取max(m[i])即為最大利潤，由于每次計算都隻需目前值以及之後的最大值，是以采用從後往前的周遊方法，一次掃描數組即可達到要求。
121-2：求解第i天賣出股票，價格為val[i],能賺取的最大利潤m[i]。[0,i]區間的最小值為min，于是m[i]=val[i]-min。最終在求取max(m[i])即為最大利潤，由于每次計算都隻需要目前值以及之前的最小值，是以采用從前往後的周遊方法，一次掃描數組也可以達到要求。
122中，可以多次購買，這就意味着能賺則賺。每次找一個極小點，然後再找最近的一個極大值，擷取一次利潤，直到數組末尾。
123實際上是121的加強版。最多兩次購買，買賣的區間不能重複，這就意味着必然有一天賣出了股票，然後再接下來的日子裡又買了一個。本題通過巧妙的設計，就能将時間複雜度降低到O(n)。具體步驟如下：
1. 用121-2的方法計算出每天賣出股票賺取的最大利潤data1;——>O(n)
2. 用121-1的方法計算出每天買入股票賺取的最大利潤data2;——>O(n)
3. 計算data2中，第i天之後的最大值，從後往前掃描，得到data3;——>O(n)
4.計算 第i天賣出的最大利潤+第i天之後買入的最大利潤=data1[i]+data3[i+1]的最大值res；——>O(n)
5. 最終傳回res即為最大值，特殊地，當i=最後一天時，data1+data3得到的是隻購買一次的值，是以無需再次考慮隻購買一次的結果。
最終算法的時間複雜度為O(n)
| class Solution { public: int maxProfit(vector<int>& prices) { int size = prices.size(); if (size == 0) return 0; int max = 0, max_price = prices[size - 1]; for (int i = size; i >= 1; i--) { if (prices[i - 1] > max_price) max_price = prices[i - 1]; else { max = (max_price - prices[i - 1] > max ? max_price - prices[i - 1] : max); } } return max; } }; |
| class Solution { public: int maxProfit(vector<int>& prices) { int size = prices.size(); if (size <= 1) return 0; if (size == 2) { return (prices[0] < prices[1] ? prices[1] - prices[0] : 0); } int max = -1, min = -1, val = 0; for (int i = 1; i <= size; i++) { if (i == 1) { if (prices[i - 1] < prices[i]) { min = prices[i-1]; } continue; } if (i == size) { if (prices[i - 1] > prices[i - 2]){ max = prices[i - 1]; if (min >= 0) { val += (max - min); } max = -1; min = -1; } continue; } if (prices[i - 1] <= prices[i - 2] && prices[i - 1] <= prices[i]) { min = prices[i - 1]; } if (prices[i - 1] >= prices[i - 2] && prices[i - 1] >= prices[i]) { max = prices[i - 1]; if (min >= 0) { val += (max - min); } max = -1; min = -1; } } return val; } }; |
| class Solution { public: int maxProfit(vector<int>& prices) { int size = prices.size(); if (size <= 1) return 0; //記錄每一天購買能夠擷取的最大利潤 vector<int> post2pre(size, 0), pre2post(size, 0); int _max = prices[size - 1], i, _min = prices[0]; for (i = size; i >= 1; i--) { _max = (prices[i - 1] > _max ? prices[i - 1] : _max); post2pre[i - 1] = _max - prices[i - 1]; } //記錄每一天賣出能夠擷取的最大利潤 for (i = 1; i <= size; i++) { _min = (prices[i - 1] < _min ? prices[i - 1] : _min); pre2post[i - 1] = prices[i - 1] - _min; } //記錄第i天之後購買入能夠擷取的最大利潤 vector<int> post2pre_max(size, 0); post2pre_max[size - 1] = post2pre[size - 1]; for (i = size - 1; i >= 1; i--) { post2pre_max[i - 1] = (post2pre[i - 1]>post2pre_max[i] ? post2pre[i - 1] : post2pre_max[i]); } //必然是在某天賣出，然後在當天之後的日子買入 int res = post2pre_max[0];//隻買一次的最大利潤 for (i = 1; i <= size-1; i++) { res = (res > (post2pre_max[i] + pre2post[i - 1]) ? res : (post2pre_max[i] + pre2post[i - 1])); } return res; } }; |
  |