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