121.Best Time to Buy and Sell Stock
给定价格曲线，进行单次买进卖出，获取最大利润。
思路一：
不断更新买入点（局部最小值），不断更新最大利润（在当前价格卖出，若获取的利润为新高则更新最大利润），直到结束。
代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int i = 0;
int max_p = 0;
int min_p = INT_MAX;
while (i < prices.size()) {
if(prices[i] < min_p) {
min_p = prices[i];
}
if(prices[i]-min_p > max_p){
max_p = prices[i] - min_p;
}
i++;
}
return max_p;
}
};
思路二：
用后一天的价格减前一天的价格，得到一个序列，相当于每一天相对于前一天的获利序列，只要求出这个序列的最大子序列即为获得的最大利润。
优化后的代码：
不用将差序列记录下来，直接筛选更新即可。
public int maxProfit(int[] prices) {
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.length; i++) {
maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
maxSoFar = Math.max(maxCur, maxSoFar);
}
return maxSoFar;
}
122.Best Time to Buy and Sell Stock II
不限购买次数，获取最大利润。
所以只要后一天相对前一天可以获利，就可以购买。将差序列中的正数累加即可。
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
int max=0;
for(int i=0;i<len-1;i++) {
if(prices[i+1] > prices[i]) {
max += prices[i+1] - prices[i];
}
}
return max;
}
};
123.Best Time to Buy and Sell Stock III
思路
因为规定最多购买两次，所以我把这道题归为找最佳临界点的题。分三种情况，购买0次，1次，2次。我把整个问题分成两部分，每部分分别用Best Time to Buy and Sell Stock I来得出最大利润。第一次在跑最后一个样例时超时了，看了一下样例，发现可以减少对连续重复数字的判断。尽管跑通了代码，时间惨不忍睹。
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len < 2) return 0;
int max_profit=0;
int profit1=0, max_profit1=0, profit2=0, max_profit2=0;
for(int i=1; i<len; i++){
profit1=0, max_profit1=0, profit2=0, max_profit2=0;
for(int j=0; j<i;){
profit1 = max(0, prices[j+1]-prices[j]+profit1);
max_profit1 = max(profit1, max_profit1);
j++;
while(j < i-1 && prices[j+1] == prices[j]){
j++;
}
}
if(len-i-1 < 2) continue;
else{
for(int k=i+1; k<len-1;){
profit2 = max(0, prices[k+1]-prices[k]+profit2);
max_profit2 = max(profit2, max_profit2);
k++;
while(k < len-1 && prices[k+1] == prices[k]){
k++;
}
}
}
max_profit = max(max_profit1+max_profit2, max_profit);
while(i < len-1 && prices[i+1] == prices[i]){
i++;
}
}
return max(max_profit1+max_profit2, max_profit);
}
};
正解
在看到我的结果是0.17%的时候是绝望的，又想了一下怎样才能更快，代码的时间复杂度是O(n2)，但我感觉这题可以O(n)过，想到了用一个数组来记录每一个时间点的最大profit，但是后续的好像又需要再算一遍，时间还是O(n2)。事实证明还是我too yong，方向是对了，还是想的太浅。
大神的做法：
第一遍正向记录每个点的最大profit，第二遍从反向记录每个点的最大利润，相加即可。这个思路和 Product of Array Except Self有点像， 两道题都是找一个中间点，计算两边的结果，通过一个数组记录结果，正向一遍，反向更新一遍。
class Solution {
public:
int maxProfit(vector<int>& p) {
if (p.size()<2) return 0;
int v=p[0];
vector<int> f(p.size(), 0);
for (int i=1; i<p.size(); ++i) {
f[i]=max(f[i-1], p[i]-v);
v=min(v, p[i]);
}
int best=f.back(), b=0;
v=p.back();
for (int i=p.size()-2; i>=0; --i) {
b=max(b, v-p[i]);
v=max(v, p[i]);
best=max(best, f[i]+b);
}
return best;
}
};
