XM3. 风口的猪-中国牛市
描述
风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。 假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。 设计算法，计算你能获得的最大收益。 输入数值范围：2<=n<=100,0<=prices[i]<=100示例1
输入:
3,8,5,1,7,8
输出:
12
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-03-07
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(vector<int> prices) {
int n = prices.size();
if(n < 2) return 0;
else if(n == 2) return max(0, prices[1] - prices[0]);
/*hxsy[i]表示第i天结束时为处于有x支股票，卖出了y支股票的状态下最大收益是多少。*/
int h0s0[n], h1s0[n], h0s1[n], h1s1[n];
memset(h0s0, 0, sizeof h0s0);
memset(h1s0, 0, sizeof h1s0);
memset(h0s1, 0, sizeof h0s1);
memset(h1s1, 0, sizeof h1s1);
/*下面的初始化非常重要，因为你做了状态限制，而为了达到某些状态比如h1s1[2],在第2天是确定的
正的就是正的，负的就是负的，不能去优化它或怎么样；
不初始化那它就是0，是和实际状态不符合的。*/
h0s0[0] = 0;
h1s0[0] = -prices[0];
h0s1[1] = prices[1] - prices[0];
h1s1[2] = -prices[2] + prices[1] - prices[0];
int res = 0;
for(int i = 1; i < n; i++){
h0s0[i] = h0s0[i - 1];
h1s0[i] = max(h1s0[i - 1], h0s0[i - 1] - prices[i]);
h0s1[i] = max(h0s1[i - 1], h1s0[i - 1] + prices[i]);
res = max(res, h0s1[i]);
if(i >= 3) h1s1[i] = max(h1s1[i - 1], h0s1[i - 1] - prices[i]);
if(i >= 3){
res = max(res, h1s1[i - 1] + prices[i]);
}
// cout<<i<<" -> "<<h0s0[i]<<" "<<h1s0[i]<<" "<<h0s1[i]<<" "<<h1s1[i]<<endl;
}
return res;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-12-23
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(vector<int> prices) {
int dp[4];
for(int i = 0; i < 4; i++) dp[i] = -prices[0];
for(int i = 0; i < prices.size(); i++){
dp[3] = max(dp[3], dp[2]+prices[i]);
dp[2] = max(dp[2], dp[1]-prices[i]);
dp[1] = max(dp[1], dp[0]+prices[i]);
dp[0] = max(dp[0], -prices[i]);
}
return dp[3];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-08-25
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(vector<int> prices) {
int first_buy_price=INT_MAX;
int first_sell_price=INT_MIN;
int second_buy_price=INT_MIN;
int second_sell_price=INT_MIN;
for(int i=0;i<prices.size();++i){
first_buy_price=min(first_buy_price,prices[i]);
first_sell_price=max(first_sell_price,-first_buy_price+prices[i]);
second_buy_price=max(second_buy_price,first_sell_price-prices[i]);
second_sell_price=max(second_sell_price,second_buy_price+prices[i]);
}
return second_sell_price;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 408KB, 提交时间: 2021-07-29
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(vector<int> prices) {
int i,mr1 = 1000,max1=0,mr2 = -1000,max2=0;
//强开上帝视角解法，即不断循环，人只能选择一次买入卖出时间，上帝可不断变换，根据当天股市情况调整自己之前的操作！
for(i=0;i<prices.size();i++){
//第一次可买入的最低损失，损失少了也就相当于受益多，即抄底购入。
if( prices[i] < mr1 )//妈的，价格竟然比我第一次买的时候便宜，应该此时才买，损失更少。
mr1 = prices[i];
//若不购入的话，看看会不会是股票涨了，且涨幅获利大于上次的获利？趁机卖掉？
else if( prices[i] - mr1 > max1 )//牛逼，涨了，卖掉。
max1 = prices[i] - mr1;
//假设此时我们将第一次的股票已经抛掉，并在此刻购入，最低损失多少可购入。
if( max1 - prices[i] > mr2 )//挣了点小钱，找个价钱低的时候再次买入
mr2 = max1 - prices[i];
//第二次卖出可能获益的最大收入
else if( mr2 + prices[i] > max2 )
max2 = prices[i] + mr2;
}
return max2;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 412KB, 提交时间: 2021-09-28
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(vector<int> prices) {
if(prices.size()<=0)
return 0;
int buy1=-prices[0];
int sell1=0;
int buy2=-prices[0];
int sell2=0;
for(int i=0;i<prices.size();i++){
buy1=max(buy1,-prices[i]);
sell1=max(sell1,prices[i]+buy1);
buy2=max(sell1-prices[i],buy2);
sell2=max(sell2,prices[i]+buy2);
}
return sell2;
}
};