题目描述
本题属于动态规划类问题。
dp数组的含义
dp[i][0]表示从第0天到第i天为止，处于持有股票的状态下，账户里的最大金额。
dp[i][1]表示从第0天到第i天为止，处于不持有股票的状态下，账户里的最大金额。
按照这个定义dp[n-1][1]就是问题的答案。
dp数组的初始化
dp[0][0] = -prices[0]; //表示买入了第0天的股票，手里账户金额是负数
dp[0][1] = 0; //表示到第0天为止，不持有股票即不买入第0天的股票的话，账户金额是0
递推公式的分析
从第0天到第i天为止，导致持有股票的状态有两种可能的原因：一是第0天到第i-1天的某一天买入了股票，对应dp[i-1][0]。二是第i天买入了股票，需要支付prices[i]。
dp[i][0] = max(dp[i-1][0],-prices[i]);
从第0天到第i天为止，导致不持有股票的状态有两种可能的原因：一是从第0天到第i-1天为止就是不持有股票的状态（此情况下，第i天没法卖出股票）。二是第i天卖出了股票，第i天能卖出股票的前提是从第0天到第i-1天为止是持有股票的状态。
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
//dp[i][0]表示从第0天到第i天为止，处于持有股票的状态下，账户里的最大金额
//dp[i][1]表示从第0天到第i天为止，处于不持有股票的状态下，账户里的最大金额
vector<vector<int>> dp(n);
for(int i = 0;i < n;i++){
dp[i].resize(2);
}
dp[0][0] = -prices[0]; //表示买入了第0天的股票，手里账户金额是负数
dp[0][1] = 0; //表示到第0天为止，不持有股票即不买入第0天的股票的话，账户金额是0
for(int i = 1;i < n;i++){
//从第0天到第i天为止，导致持有股票的状态有两种可能的原因，
//一是第0天到第i-1天的某一天买入了股票，对应dp[i-1][0]
//二是第i天买入了股票，需要支付prices[i]
dp[i][0] = max(dp[i-1][0],-prices[i]);
//从第0天到第i天为止，导致不持有股票的状态有两种可能的原因：
//一是从第0天到第i-1天为止就是不持有股票的状态（此情况下，第i天没法卖出股票）
//二是第i天卖出了股票，第i天能卖出股票的前提是从第0天到第i-1天为止是持有股票的状态
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return dp[n-1][1];
}
};