風(fēng)口的豬-中國(guó)牛市（小米2016校招）

---

1、題目描述
風(fēng)口之下，豬都能飛。當(dāng)今中國(guó)股市牛市，真可謂“錯(cuò)過等七年”。 給你一個(gè)回顧歷史的機(jī)會(huì)，已知一支股票連續(xù)n天的價(jià)格走勢(shì)，以長(zhǎng)度為n的整數(shù)數(shù)組表示，數(shù)組中第i個(gè)元素（prices[i]）代表該股票第i天的股價(jià)。 假設(shè)你一開始沒有股票，但有至多兩次買入1股而后賣出1股的機(jī)會(huì)，并且買入前一定要先保證手上沒有股票。若兩次交易機(jī)會(huì)都放棄，收益為0。 設(shè)計(jì)算法，計(jì)算你能獲得的最大收益。 輸入數(shù)值范圍：2<=n<=100,0<=prices[i]<=100

輸入例子:
3,8,5,1,7,8

輸出例子:
12

---

2、代碼：

#include <iostream> #include <vector> #include <algorithm> using namespace std; int calculateMax(vector<int> prices) {int len = prices.size();vector<int> maxLeft(len,0);//Left to rightfor (int i = 1, minPos = 0;i < len;++i){if (prices[i] > prices[i - 1]){maxLeft[i] = max(maxLeft[i - 1], prices[i] - prices[minPos]);}else{maxLeft[i] = maxLeft[i - 1];if (prices[i] < prices[minPos]){minPos = i;}}}//Right to leftvector<int> maxRight(len, 0);maxRight[len - 1] = 0;for (int i = len - 2, maxPos = len - 1;i >= 0;--i){if (prices[i] < prices[i + 1]){maxRight[i] = max(maxRight[i + 1], prices[maxPos] - prices[i]);}else{maxRight[i] = maxRight[i + 1];if (prices[i] > prices[maxPos]){maxPos = i;}}}int res=0;for (int i = 0;i < len;++i){res = max(res, maxLeft[i] + maxRight[i]);}return res; }int main() {int ia;vector<int> v;while (cin >> ia){v.push_back(ia);}cout << calculateMax(v) << endl;system("pause");return 0; }

---

3、總結(jié)：
參考了兩個(gè)解答寫出，實(shí)在感嘆自身實(shí)力不足。
A、從左至右掃描得到每天能收益的最大值，記數(shù)組maxLeft，此時(shí)我們要以最小值為基準(zhǔn)；從右至左掃描得到每天能收益的最大值，記數(shù)組maxRight，此時(shí)我們要以最大值為基準(zhǔn)。返回每天兩數(shù)組和的最大值。
注意點(diǎn)：結(jié)果中Left部分相當(dāng)于是第一次獲得的最大收益，Right則是第二次。這個(gè)想法對(duì)目前的我太難。這個(gè)解答方式是我主要參考的思路。

B、這個(gè)思路很自然，但是我竟然沒有想到。以i=1開始，求i前面最大收益，求i后面最大收益，記錄最大和。然后++i，不斷更新最大和，結(jié)束時(shí)返回最大和。求最大收益：i=3,k=1,j=0，更新max,k=2,j=0,1，更新max……不斷求取前后最大，滿足手里始終只有一支股。

總結(jié)

以上是生活随笔為你收集整理的风口的猪-中国牛市（小米2016校招）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。