力扣121. 买卖股票的最佳时机（动态规划）
动态规划：
有点像0-1背包问题：
买入：
i当天买入i当天不买入
i当天买入的最大收益-i当天的股价i-1买入的最大收益，维持现状in[i]-prices[i]in[i-1]
卖出：
i当天卖出i当天不卖出
i当天卖出的最大收益i-1天买入的最大收益+i当天的股价i-1天卖出的最大收益，维持原状out[i]out[i-1]+prices[i]out[i-1]
i-1天买入的最大收益，这里很多人不理解，以为仅仅是前一天的价格，其实i-1天买入的最大收益已经取最大值，即i-1天买入的最大收益代表第一天到第i-1天的最佳买入点，只是没有标记哪一天，直接相加即可。
复杂度分析：
时间复杂度:O(N)空间复杂度:O(N)
//
// main.cpp
// 121maxProfit
//
// Created by MXQ on 2020/10/21.
//
#include <iostream>
#include<vector>
using namespace::std;
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
if(n==0 || n==1)return 0;
vector<int>in(n);
vector<int>out(n);
out[0]=0;
in[0]=-prices[0];
int maxoutvalue=0;
for (int i=1; i<n; i++) {
//转移方程
in[i]=max(-prices[i],in[i-1]);
out[i]=max(in[i-1]+prices[i],out[i-1]);
if (out[i]>maxoutvalue) {
maxoutvalue=out[i];
}
}
return maxoutvalue;
}
};
int main(int argc, const char * argv[]) {
// insert code here...
vector<int>prices={7,6,4,3,1};
Solution s;
auto result=s.maxProfit(prices);
std::cout << result<<endl;
std::cout << "Hello, World!\n";
return 0;
}
