leetcode面试题63. 股票的最大利润(dp+迭代)
目录
- 题目来源
- 解题方法
- 动态规划
- 迭代
题目来源
解题方法
动态规划
我们首先需要考虑的是dp数组的选取，在每一天都分为持有股票和未持有股票两种情况，因此我们可以选择dp[n][2]作为数组，dp[i][0]表示前i天未持有股票的最大利润，dp[i][1]表示前i天持有股票的最大利润
第i天未持有股票，很可能是前i-1天未持有，第i天也不买入；也有可能是前i-1天持有了，第i天卖掉
第i天持有股票，有可能是前i-1天未持有，第i天买入；也有可能是前i-1天就持有了，第i天不卖出
直接上代码，非常清晰，我们只需要取第n-1天未持有股票的最大利润即可
class Solution {
public:int maxProfit(vector& prices) {if(prices.size()==0)return 0;int n=prices.size();int dp[n][2];dp[0][0]=0;dp[0][1]=-prices[0];for(int i=1;i 迭代
思路：我们只需要找出最小的股票价格，计算买入以后的每一天的利润，取最大的利润即可
class Solution {
public:int maxProfit(vector& prices) {if(prices.size()==0)return 0;int minPrice=INT_MAX;int maxProfit=INT_MIN;for(int i=0;i 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！