121. 买卖股票的最佳时机
要求：
[7,1,5,3,6,4]
在里面找出合适的买入和卖出的时机
思路：
找到最小值和最大值，直接做差，但是需要保证顺序
贪心算法：
巧妙之处：
每一个节点都要比对是否是最小节点，然后跟最小节点进行相减，看是否是最大值
代码：
int maxProfit(vector<int>& prices) { int low = INT_MAX; int result = INT_MIN; for (int i = 0; i < prices.size(); i++) { low = min(low, prices[i]); result = max(result, prices[i] - low); } return result; }
动态规划
持有：dp[n][0]
不持有：dp[n][1]
因为只买入一次，所以是-prices[i]
dp[i][0] = max(-prices[i], dp[i-1][0]);
dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1]);
代码：
1 int maxProfit(vector<int>& prices) { 2 vector<vector<int>> dp(prices.size(), vector<int>(2, 0)); 3 4 dp[0][0] = -prices[0]; 5 dp[0][1] = 0; 6 7 for (int i = 1; i < prices.size(); i++) 8 { 9 // 持有 10 dp[i][0] = max(- prices[i], dp[i - 1][0]); 11 // 不持有 12 dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1]); 13 } 14 15 return max(dp[prices.size() - 1][0], dp[prices.size() - 1][1]); 16 }