买卖股票的最佳时机
贪心算法
核心思想是找到利润。然后利润大于0的相加
class Solution { public: int maxProfit(vector<int>& prices) { vector<int> profit; int result = 0; for(int i=1 ;i < prices.size(); i++) { if(prices[i] - prices[i-1] > 0 ) //单日利润大于0的存入 profit.push_back(prices[i] - prices[i-1]); } for(int i=0 ; i < profit.size(); i++) //计算利润和 result += profit[i]; return result; } };
动态规划
dp数组的含义：
- dp[i][0] 表示第i天持有股票所得现金。
- dp[i][1] 表示第i天不持有股票所得最多现金
如果第i天持有股票即dp[i][0]
- 第i-1天就持有股票，那么就保持现状，即：dp[i - 1][0]
- 第i天买入股票，就是昨天不持有股票的所得现金减去今天的股票价格
即：dp[i - 1][1] - prices[i]
如果第i天不持有股票即dp[i][1]的情况
- 第i-1天就不持有股票，那么就保持现状，即：dp[i - 1][1]
- 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金
即：prices[i] + dp[i - 1][0]
class Solution { public: int maxProfit(vector<int>& prices) { if(prices.size()<=1) return 0; vector<vector<int>> dp(prices.size() , vector<int>( 2,0 ) ); dp[0][0] = -prices[0]; dp[0][1] = 0; for(int i=1 ; i<prices.size() ;i++) { dp[i][0] = max( dp[i-1][0] , dp[i-1][1] - prices[i] ); dp[i][1] = max( dp[i-1][1] , dp[i-1][0] + prices[i] ); } return dp[prices.size()-1][1]; } };
二刷
class Solution { public: int maxProfit(vector<int>& prices) { if(prices.size()==0) return 0; vector<vector<int>> dp(prices.size(),vector<int>(2,0)); dp[0][0] = 0; dp[0][1] = -prices[0]; for(int i=1 ; i<prices.size() ;i++) { dp[i][0] = max(dp[i-1][0] , dp[i-1][1]+prices[i]); dp[i][1] = max(dp[i-1][1] , dp[i-1][0]-prices[i]); } return max(dp[prices.size()-1][0],dp[prices.size()-1][1]); } };
