风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。
给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，
数组中第i个元素（prices[i]）代表该股票第i天的股价。 假设你一开始没有股票，
但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。
若两次交易机会都放弃，收益为0。 设计算法，计算你能获得的最大收益。
输入数值范围：2< =n<=100,0<=prices[i]<=100
输入例子:
3,8,5,1,7,8
输出例子:
12
C++
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(vector<int> prices) {
int first, first_max;
int second, second_max;
int max;
max = 0;
for (int i=0; i<prices.size(); i++)
for (int j=i; j<prices.size(); j++){
// 进行第一次股票交易的计算
first = prices[j] - prices[i];
// 如果第一次股票交易的卖出股票已经到了倒数第二个，就没必要计算第二次交易了
if (j == (prices.size()-1)){
second = 0;
if ((first + second) > max)
max = first + second;
continue;
}
else
// 进行第二次股票交易的计算
for (int p=j+1; p<prices.size(); p++)
for (int q=p; q<prices.size(); q++){
second = prices[q] - prices[p];
if ((first + second) > max)
max = first + second;
}
}
return max;
}
};
/*
解题思路：
做大循环，
第一次的股票交易收益=j位置（不断向右移）减去当前位置（不断向右移）
第二次的股票交易收益=q位置（不断向右移）减去当前位置（该位置大于j）（不断向右移）
做大循环其实不好，时间复杂度太高。
*/
另一种时间复杂度为O(n)的算法
// 别人的思路，我添加的注释
class Solution {
public:
int calculateMax(vector<int> prices) {
vector<int> v(prices.size(), 0);
int min_prices = prices[0]; // 最小的点，初始值为数组的第一个点
int max_prices = prices[prices.size() - 1]; // 最大的点。初始值为数组的最后一个点
int max_profit = 0; // 最大的收益
// 从第二个位置开始(i=1表示第二个位置开始)，求出当前的点(往前)最大收益
// 当前点的最大收益可能是在之前的位置得到的(即当前位置不影响最大收益)，所以需要和max_profit比较
// 当前位置的最大收益=最大收益=max(最大收益，当前位置的值-之前位置的最小值)
for (int i = 1; i < prices.size(); ++i) {
v[i] = max_profit = max(max_profit, prices[i] - min_prices);
min_prices = min(prices[i], min_prices); // 更新最小位置点
}
// 从最后一个位置开始，求出当前点(往后)的最大收益
// 同理，当前点的最大收益可能是在之后的位置得到的，所以需要和max_profit比较
// 当前位置的最大收益=最大收益=max(最大收益，之后位置的最大值-当前位置的值)
// v[i] += max_profit; 表示该点的【最后最大收益】=往前的最大收益+往后的最大收益
/*
注:其实v[i] += max_profit这个有点说不过去，
因为i可能是卖出股票的一天，同时是买到股票的一天，不能再某一天卖了又买，
但是这样不影响最大值，因为如果这天卖了又买的话，相当于没有经过这一天
*/
max_profit = 0;
for (int i = prices.size() - 2; i >= 0; --i) {
max_profit = max(max_profit, max_prices - prices[i]);
v[i] += max_profit;
max_prices = max(max_prices, prices[i]); // 更新最大位置点
}
// 求出哪个点最大
int profit = v[0];
for (int i = 1; i < prices.size() - 1; ++i) {
profit = max(profit, v[i]);
}
return profit;
}
};
/*
解题思路：
这个方式十分巧妙，用了时间复杂度O(n)就算出了一次股票交易的最大值
再用两面往中间走的方式，求出两次的最大值
如果需要求出交易的点，只需要求出交易最大值的那段的两个端点即可，
如果两个【都】不等于原数组的两个端点的话，那么交易的点是：
起始点，最大值线段的起始点，最大值线段的终点，终点
如果只有两个点的话，那么一端为起始点(或者中间的某个点)，另一端为中间某个点(或者终点)
*/