本文最后更新于:2021年2月25日 中午
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例 1:
| 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
|
示例 2:
| 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
|
Solution
| class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); int res=0; for(int i=0; i<n; ++i){ for(int j=i+1; j<n; ++j) res = max(res, prices[j]-prices[i]); } return res; } };
|
- 贪心算法
- 假如计划在第 i 天卖出股票,那么最大利润的差值一定是在[0, i-1] 之间选最低点买入;所以遍历数组,依次求每个卖出时机的的最大差值,取最大值。
- 贪心的想法就是取最左最小值,取最右最大值,那么得到的差值就是最大利润。
| class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); int minPrice = 1e9, maxProf = 0; for(int i : prices){ maxProf = max(maxProf, i-minPrice); minPrice = min(minPrice, i); } return maxProf; } };
|
动态规划
参考 @liweiwei1419 、代码随想录
- 定义状态
- 推导状态转移方程
- 确定初始状态 base case
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if(n<2) return 0;
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0; dp[0][1] = -prices[0]; for(int i=1; i<n; ++i){ dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]); dp[i][1] = max(dp[i-1][1], -prices[i]); } return dp[n-1][0]; } };
|
| class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); vector<vector<int>> dp(2, vector<int>(2, 0)); dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; ++i) { dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1]+prices[i]); dp[i % 2][1] = max(dp[(i - 1) % 2][1], -prices[i]); } return dp[(n - 1) % 2][0]; } };
|