一、题目
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
二、思路
遇到动态规划依旧满头大汗，即使只是简单也很吃力吗…
做了1h左右吧，前面整理了一下思路，大致确定的流程是：外层找前面的最小购入价，内层找后面的最大出售价，然后dp取上次和本次的最大值，这样dp[prices.size()-2]就是最优值了。
然后编码的时候就感觉，每次反复在内层寻找最大出售值有点太蠢了，复杂度O(n2)太高，即使加上了个判定条件，也还是果不其然的TLE了。
后面就在想，如何让前半段（购入）和后半段（出售）达成统一的进退呢，如同外层算_buy一般，通过一次遍历就选取到每个位置的最优值。
最后还是采用了最直白的方法，先从后向前遍历一次prices，记录下每个位置的_sell最大值，然后在遍历_buy时就能够同步的选择最优的购入和售出了。
三、尝试
通过的测试用例：208 / 212 个（TLE）
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> dp(prices.size(),0);
dp[0]=0;
int _buy=10001;
int _sell=0;
if(prices.size()<=1){
return 0;
}
for(int i=1;i<prices.size();i++){
_sell=max(prices[i],_sell);
}
for(int i=0;i<prices.size()-1;i++){
_buy=min(prices[i],_buy);
if(i>=1&&prices[i-1]==_sell){
_sell=0;
for(int j=i+1;j<prices.size();j++){
_sell=max(prices[j],_sell);
}
}
if(i>=1){
dp[i]=max(_sell-_buy,dp[i-1]);
}
else dp[i]=max(_sell-_buy,dp[0]);
}
return dp[prices.size()-2];
}
};
四、题解
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> dp(prices.size(),0);
vector<int> _sell(prices.size()+1,0);
int _buy=prices[0];
if(prices.size()<=1){
return 0;
}
for(int j=prices.size()-1;j>=1;j–){
_sell[j]=max(prices[j],_sell[j+1]);
}
dp[0]=max(_sell[1]-_buy,0);
for(int i=1;i<prices.size()-1;i++){
_buy=min(prices[i],_buy);
dp[i]=max(_sell[i]-_buy,dp[i-1]);
}
return dp[prices.size()-2];
}
};
