首页 > 试题广场 >

买卖股票的最好时机(三)

[编程题]买卖股票的最好时机(三)
  • 热度指数：37568 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费

数据范围：，股票的价格满足
要求: 空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度
示例1

输入

[8,9,3,5,1,3]

输出

4

说明

第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2
第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2
总收益为4。
示例2

输入

[9,8,4,1]

输出

0
示例3

输入

[1,2,8,3,8]

输出

12

说明

第一笔股票交易在第一天买进，第三天卖出；第二笔股票交易在第四天买进，第五天卖出；总收益为12。
因最多只可以同时持有一只股票，所以不能在第一天进行第一笔股票交易的买进操作，又在第二天进行第二笔股票交易的买进操作（此时第一笔股票交易还没卖出），最后两笔股票交易同时在第三天卖出，也即以上操作不满足题目要求。

备注:
总天数不大于200000。保证股票每一天的价格在[1,100]范围内。
算法知识视频讲解
添加回答
Java
愿每个人都能被温柔以待头像 愿每个人都能被温柔以待 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n=prices.length;
        int buy1=Integer.MIN_VALUE,buy2=Integer.MIN_VALUE;
        int sell1=0,sell2=0;
        for(int curPrice:prices){
            // buy1  记录 当前买入的最少花费 -cost ；
            // sell1 记录 交易一次的最大收益值 max_profit1 ;
            // buy2  记录 交易一次的收益-当前买入的最大值 ；
            // sell2 记录 交易两次的最大收益值 max_profit2 ；
            buy1=Math.max(buy1,(-1)*curPrice);
            sell1=Math.max(sell1,curPrice+buy1);
            buy2=Math.max(buy2,sell1-curPrice);
            sell2=Math.max(sell2,curPrice+buy2);
            System.out.println("buy1:" + buy1 + "    sell1:" +sell1+ "     buy2:"+ buy2 +  "    sell2:" + sell2);
        }
        return sell2;
// =========================================================
//         buy1:-8    sell1:0     buy2:-8    sell2:0
//         buy1:-8    sell1:1     buy2:-8    sell2:1
//         buy1:-3    sell1:1     buy2:-2    sell2:1
//         buy1:-3    sell1:2     buy2:-2    sell2:3
//         buy1:-1    sell1:2     buy2:1     sell2:3
//         buy1:-1    sell1:2     buy2:1     sell2:4
// =========================================================     
    }
}
发表于 2021-07-31 23:31:39 回复(0)
Java
花落梦里头像 花落梦里 
    public int maxProfit (int[] prices) {
        int n=prices.length;
        int buy1=Integer.MIN_VALUE,buy2=Integer.MIN_VALUE;
        int sell1=0,sell2=0;
        for(int p:prices){//之前最大卖出价格，和在当天卖出的价格进行对比
            buy1=Math.max(buy1,(-1)*p);
            sell1=Math.max(sell1,p+buy1);
            buy2=Math.max(buy2,sell1-p);
            sell2=Math.max(sell2,p+buy2);
        }
        return sell2;
    }

发表于 2021-03-27 09:45:30 回复(4)
Java
Sugar666头像 Sugar666
动态规划： 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        // 买卖两次，需要使用到三元数组
        
        if(prices.length == 0) {
            return 0;
        }
        
        // 0表示不持有，1表示持有
        // dp[天数][交易的次数][持有的状态]
        int[][][] dp = new int[prices.length][3][2];
        
        // 初始化
        for(int i = 0;i <= 2;i++) {
            // 不持有的时候 为0
            dp[0][i][0] = 0;
            // 持有的时候，为第一天的值
            dp[0][i][1] = -prices[0];
        }

        for(int i = 1;i < prices.length;i++) {
            for(int k = 0;k <= 2;k++) {
                // 交易0次
                if(k == 0) {
                    // 不可能的值，赋值为MIN_VALUE
                    dp[i][k][1] = Integer.MIN_VALUE;
                    dp[i][k][0] = 0;
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i-1][k][0],dp[i-1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i]); 
            }
        }
        return dp[prices.length - 1][2][0];
    }
}


发表于 2021-01-04 21:38:13 回复(2)
Python 3
Vivimore头像 Vivimore

到第i天为止的5种状态：

  • dp[i][0]表示到第i天为止没有买过股票的最大收益
  • dp[i][1]dp[i][1]dp[i][1]表示到第i天为止买过一次股票还没有卖出的最大收益
  • dp[i][2]dp[i][2]dp[i][2]表示到第i天为止买过一次也卖出过一次股票的最大收益
  • dp[i][3]dp[i][3]dp[i][3]表示到第i天为止买过两次只卖出过一次股票的最大收益
  • dp[i][4]dp[i][4]dp[i][4]表示到第i天为止买过两次同时也买出过两次股票的最大收益
    收益可能为负数，可能交易二次的收益大，也可能交易一次收益最大
    class Solution:
  def maxProfit(self , prices: List[int]) -> int:
      res = 0
      n = len(prices)
      dp = [[-10000]*5 for i in range(n)]
      dp[0][0] = 0
      dp[0][1] = -prices[0]
      for i in range(1, n):
          dp[i][0] = dp[i-1][0]
          dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
          dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
          dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
          dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
      return max(dp[n-1][2], dp[n-1][4], 0)
发表于 2022-06-24 11:32:44 回复(1)
Python 3
牛客35961088号头像 牛客35961088号 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if not prices: return 0
        buy1 = -prices[0]
        buy2 = -prices[0]
        sell1, sell2 = 0, 0
        for i in range(1, len(prices)):
            buy1 = max(buy1, -prices[i])
            sell1 = max(sell1, buy1+prices[i])
            buy2 = max(buy2, sell1-prices[i])
            sell2 = max(sell2, buy2+prices[i])
        return sell2

发表于 2021-08-06 10:43:18 回复(1)
w浩头像 w浩 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int len = prices.size();
        if(len<1) return 0;
        int b1 = prices[0];
        int s1 = 0;
        int b2 = prices[0];
        int s2 = 0;
        for(int i =1;i<len;i++){
            b1 = min(b1,prices[i]);
            s1 = max(s1,prices[i]-b1);
            b2 = min(b2,prices[i]-s1);
            s2 = max(s2,prices[i] - b2);
        }
        return max(s1,s2);
    }
};

发表于 2021-04-19 20:45:57 回复(0)
Java
拥有广大的未来头像 拥有广大的未来
为什么编译失败呀？，帮帮孩子吧
发表于 2022-09-25 20:16:31 回复(0)
高乐高的高头像 高乐高的高
关键是怎么处理两次交易机会。
思路是一次正向计算一次买入卖出的收益，一次反向计算一次买入卖出的收益。相遇点即为当前分割下的最佳收益。 
class Solution:
    def maxProfit(self , prices ):
        m=prices[0]
        forward=[0]
        for price in prices:
            m=min(m,price)
            forward.append(max(forward[-1],price-m))
        prices.reverse()
        m=prices[0]
        backward=[0]
        for price in prices:
            m=max(m,price)
            backward.append(max(backward[-1],m-price))
        backward.reverse()
        profit=0
        for i in range(len(forward)):
            cp = forward[i]+backward[i]
            if cp>profit:
                profit=cp
        return profit
有个问题，如果是三次买入卖出，还有讨巧的余地吗？


发表于 2020-11-14 11:17:47 回复(3)
C++
算法小白一枚555头像 算法小白一枚555 
#include "iostream"
#include "vector"
using namespace std;
//问题描述：在买股票2的基础上，最多允许2次买卖交易，但是在卖之前必须保证之前买入的股票已经卖出去了
int maxProfit(vector<int>& prices)
{
    //这里dp变成一个nx5大小的矩阵，
    //一天一共就有五个状态，
    //0.没有操作
    //1.第一次买入
    //2.第一次卖出
    //3.第二次买入
    //4.第二次卖出
    vector<vector<int>> dp(prices.size()+1,vector<int>(5,0));

    dp[0][0]=0;//没有操作，那利润就是0
    dp[0][1]=-prices[0];//第0天进行第一次买入，利润是-prices[0]
    dp[0][2]=0;//第0天进行第一次卖出，但是之前还没有买入任何股票，因此卖出的是空气，利润是0
    dp[0][3]=-prices[0];//第0天进行第二次买入，在此之前一定进行了第一次卖出，可以理解为在第0天进行了买入和卖出操作，利润是0，然后进行了第二次买入操作
    dp[0][4]=0;//第0天进行第二次卖出，利润依旧是0
    for(int i=1;i<prices.size();i++)
    {
        //达到dp[i][1]状态，有两个具体操作：
        //操作一：第i天第一次买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
        //操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
        //达到dp[i][2]也有两个操作：
        //操作一：第i天第一次卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
        //操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
        dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);
        //达到dp[i][3]也有两个操作：
        //操作一：第i天第二次买入股票了，那么dp[i][3] = dp[i - 1][2] - prices[i]
        //操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][3] = dp[i - 1][3]
        dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]);
        //达到dp[i][4]也有两个操作：
        //操作一：第i天第二次卖出股票了，那么dp[i][4] = dp[i - 1][3] + prices[i]
        //操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][4] = dp[i - 1][4]
        dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);
    }
    return dp[prices.size()-1][4];
}
//空间优化：滚动数组
int maxProfit2(vector<int>& prices)
{
    int* dp=new int[5];
    dp[0]=0;
    dp[1]=-prices[0];
    dp[2]=0;
    dp[3]=-prices[0];
    dp[4]=0;
    for(int i=1;i<prices.size();i++)
    {
        dp[1]=max(dp[1],dp[0]-prices[i]);
        dp[2]=max(dp[2],dp[1]+prices[i]);
        dp[3]=max(dp[3],dp[2]-prices[i]);
        dp[4]=max(dp[4],dp[3]+prices[i]);
    }
    return dp[4];
}
int main()
{
    return 0;
}

发表于 2023-08-06 15:02:52 回复(0)
C++
Spectre_头像 Spectre_ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // 时间复杂度O(N)，空间复杂度O(N)
        vector<vector<int>> dp(4, vector<int>(prices.size(), -10000));
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            dp[0][i] = max(dp[0][i - 1], -prices[i]);
            dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i]);
            dp[2][i] = max(dp[2][i - 1], dp[1][i - 1] - prices[i]);
            dp[3][i] = max(dp[3][i - 1], dp[2][i - 1] + prices[i]);
        }
        return max(0, max(dp[1][prices.size() - 1], dp[3][prices.size() - 1]));
    }
};

发表于 2022-11-09 14:55:09 回复(0)
Python3
JianYue头像 JianYue 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 两次交易所能获得的最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        b1, s1, b2, s2 = -prices[0], 0, -prices[0], 0
        for p in prices:
            b1 = max(b1, -p)
            s1 = max(s1, b1+p)
            b2 = max(b2, s1-p)
            s2 = max(s2, b2+p)
        return max(s2, 0)

发表于 2022-10-05 22:36:18 回复(0)
余生还长着呢头像 余生还长着呢 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        // 状态定义dp[i][5]：表示每天可能存在的5种买卖状态
        // dp[i][0]表示到第i天为止没有买过股票的最大收益
        // dp[i][1]表示到第i天为止买过一次股票还没有卖出的最大收益
        // dp[i][2]表示到第i天为止买过一次也卖出过一次股票的最大收益
        // dp[i][3]表示到第i天为止买过两次只卖出过一次股票的最大收益
        // [i][4]表示到第i天为止买过两次同时也买出过两次股票的最大收益
        int dp[][] = new int[prices.length][5];

        // 初始化
        Arrays.fill(dp[0],-100000);

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        // 状态转移
        for(int i = 1; i < prices.length;i++){
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2],dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3],dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4],dp[i - 1][3] + prices[i]);
        }

        return Math.max(dp[prices.length - 1][2],Math.max(dp[prices.length - 1][4],0));
    }
}

编辑于 2024-02-19 11:31:57 回复(0)
牛客2024007号头像 牛客2024007号 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        // 定义子问题：交易后的最大利润，但是这题状态比较多
        int len = prices.length;
        int[][][] dp = new int[len + 1][2][3];
        int res = 0;
        dp[0][1][1] = Integer.MIN_VALUE; // 未发生交易就持有仓位，不可能
        dp[0][1][2] = Integer.MIN_VALUE; // 未发生交易就持有仓位，不可能
        for(int i = 1; i <= len; i++) {
            // 0 未发生交易， 1 第一次交易后， 2 第二次交易后
            // 1 - 持有， 0 - 不持有
            dp[i][0][0] = dp[i - 1][0][0];
            // 第一次交易后，持有仓位
            dp[i][1][1] = Math.max(dp[i - 1][0][0] - prices[i - 1], dp[i - 1][1][1]);
            // 第一次交易后，空仓
            dp[i][0][1] = Math.max(dp[i - 1][0][1], dp[i - 1][1][1] + prices[i - 1]);
            // 第二次交易后，持有仓位
            dp[i][1][2] = Math.max(dp[i - 1][1][2], dp[i - 1][0][1] - prices[i - 1]);
            // 第二次交易后，空仓
            dp[i][0][2] = Math.max(dp[i - 1][0][2], dp[i - 1][1][2] + prices[i - 1]);
            
        }
        return Math.max(dp[len][0][2], Math.max(dp[len][0][1], 0));
    }
}
发表于 2024-01-10 21:34:53 回复(0)
Go
NightCruising头像 NightCruising

BM81的升级版

func maxProfit(prices []int) int {
    own1, los1, own2, los2 := -prices[0], 0, -prices[0], 0
    for i := 1; i < len(prices); i++ {
        own1, los1, own2, los2 = Max(own1, -prices[i]), Max(los1, own1+prices[i]), Max(own2, los1-prices[i]), Max(los2, own2+prices[i])
    }
    return los2
}
编辑于 2024-01-10 01:26:16 回复(0)
牛客289414281号头像 牛客289414281号
滑动窗口，每次找到一个连续上升区间，然后获取差值，遍历完所有区间，找出差值最大的2个相加 就可以了
int left=0;
 int right=0;
 int max=0;
 int smax=0;
 while (left<prices.length-1){
     while (left+1<prices.length&&prices[left]>prices[left+1]){
           left++;
         }
    right=left+1;
     while (right+1<prices.length&&prices[right]<prices[right+1]){
        right++;
     }
    if(left<prices.length&&right<prices.length){
        int tmp=prices[right]-prices[left];
         if(tmp>max){
            max=tmp;
         }else if(tmp>smax){
            smax=tmp;
         }
    }
    left=right+1;
 }
System.out.println(max+smax);
}

发表于 2023-11-29 15:48:02 回复(0)
C++
牛客706368877号头像 牛客706368877号
动态规划，然后优化空间复杂度。 
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int n = prices.size();
        if (n < 2) {
            return 0;
        }

        int dp0Prev = -prices[0], dp0;
        int dp1Prev = 0, dp1;
        int dp2Prev = -prices[0], dp2;
        int dp3 = 0;
        for (int i = 1; i < n; ++i) {
            dp0 = max(dp0Prev, -prices[i]);
            dp1 = max(dp1Prev, dp0Prev + prices[i]);
            dp2 = max(dp2Prev, dp1Prev - prices[i]);
            dp3 = max(dp3, dp2Prev + prices[i]);
            dp0Prev = dp0;
            dp1Prev = dp1;
            dp2Prev = dp2;
        }

        return max(0, max(dp1, dp3));
    }
};


发表于 2023-09-24 16:26:25 回复(0)
C#
实习小子_头像 实习小子_
只使用两个dp数组，dp1代表第 i 天卖出的最大利润，dp2代表第i天及之后买入的最大利润。
买卖两次就是 第i天卖出和第i+1天之后买入的最大利润和的最大值。 
using System;
using System.Collections.Generic;

class Solution {
    public int maxProfit (List<int> prices) {
        int n = prices.Count;
        int[] dp1 = new int[n];
        int[] dp2 = new int[n + 1];
	    for (int i = n-1; i > 0; i--)
		    prices[i] = prices[i] - prices[i-1];

        for (int i = 1; i < n; i++)
            dp1[i] = Math.Max(prices[i], dp1[i - 1] + prices[i]);

        dp2[n] = 0;
        for (int i = n - 1; i >= 1; i--)
            dp2[i] = Math.Max(prices[i], dp2[i + 1] + prices[i]);

        for (int i = n - 1; i >= 1; i--)
            dp2[i] = Math.Max(dp2[i + 1], dp2[i]);

        int max = 0;
        for (int i = 1; i < n; i++)
            if (dp1[i] + dp2[i + 1] > max) max = dp1[i] + dp2[i + 1];

        return max;
    }
}


发表于 2023-09-17 16:57:25 回复(0)
Java
悟空GGG头像 悟空GGG
每一天我们都尽可能地买入最低价股票，并且尽可能地用最高价卖出。对于第二次交易，我们把第一次交易的盈利放入第二次交易的成本中(做差，第二次的成本减第一次的盈利prices[i]−sell1)，那么我们第二次交易的的盈利就是两次交易的盈利。 
    public int maxProfit (int[] prices) {
        // write code here
        int buy1 = Integer.MAX_VALUE;
        int buy2 = Integer.MAX_VALUE;
        int sell1 = 0;
        int sell2 = 0;

        for(int price : prices) {
            buy1 = Math.min(buy1,price);
            sell1 = Math.max(sell1,price-buy1);
            buy2 = Math.min(buy2,price - sell1); //在第二次买的时候，价格其实是考虑用了第一次赚的钱去补贴一部分的
            sell2 = Math.max(sell2,price - buy2);
        }
        return sell2;
    }


发表于 2023-07-23 19:22:17 回复(0)
不让我进拉倒头像 不让我进拉倒 
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        # 动态规划
        # dp[i][j]表示第i天交易了j次的最大收益
        # 因为最多交易两次，每次包括买入卖出两个动作，因此j<=4
        # 因为1<=val<=10^5,所以可以用-10000表示无穷小
        dp = [[-10000] * 5 for _ in range(len(prices))]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, len(prices)):
            dp[i][0] = dp[i - 1][0]
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
        # 返回交易一次或者交易两次较大的那个
        return max(dp[-1][2], dp[-1][4])

发表于 2023-07-05 14:27:40 回复(0)
C#
mkr67n头像 mkr67n

递推dp

using System;
using System.Collections.Generic;

class Solution {
    public int maxProfit (List<int> prices) {
        const int maxK = 2;
        var dp = new int[prices.Count + 1, maxK + 1, 2];

        // dp[0,  x, 0] => 0
        // dp[0,  x, 1] => -inf
        // dp[>0, 0, 0] => 0
        // dp[>0, 0, 1] => -inf
        for (int j = 0; j <= maxK; j++)
        {
            dp[0, j, 0] = 0;
            dp[0, j, 1] = int.MinValue;
        }
        for (int day = 1; day <= prices.Count; day++)
        {
            dp[day, 0, 0] = 0;
            dp[day, 0, 1] = int.MinValue;
        }

        for (int day = 1; day <= prices.Count; day++)
            for (int j = 1; j <= maxK; j++)
            {
                //如果买入，消耗一次次数
                dp[day, j, 1] = Math.Max(dp[day - 1, j, 1], dp[day - 1, j - 1, 0] - prices[day - 1]);
                //卖出不应重复扣次数
                dp[day, j, 0] = Math.Max(dp[day - 1, j, 0], dp[day - 1, j, 1] + prices[day - 1]);
            }
        return dp[prices.Count, maxK, 0];
    }
}

空间优化

using System;
using System.Collections.Generic;

class Solution {
    public int maxProfit (List<int> prices) {
        const int maxK = 2;
        var dp = new int[maxK + 1, 2];

        for (int j = 0; j <= maxK; j++)
        {
            dp[j, 0] = 0;
            dp[j, 1] = int.MinValue;
        }

        for (int day = 1; day <= prices.Count; day++)
        {
            var pre_day_j_0 = 0; // dp[day - 1, j - 1, 0]
            for (int j = 1; j <= maxK; j++)
            {
                // dp[day, j, 1] = Math.Max(dp[day - 1, j, 1], dp[day - 1, j - 1, 0] - prices[day - 1]);
                // dp[day, j, 0] = Math.Max(dp[day - 1, j, 0], dp[day - 1, j, 1] + prices[day - 1]);
                var curr_day_j_0 = dp[j, 0];
                dp[j, 0] = Math.Max(dp[j, 0], dp[j, 1] + prices[day - 1]); // 用到上次的dp[j, 1]（原dp[day - 1, j, 1]）因此先更新该状态
                dp[j, 1] = Math.Max(dp[j, 1], pre_day_j_0 - prices[day - 1]);
                pre_day_j_0 = curr_day_j_0;
            }
        }
        return dp[maxK, 0];
    }
}
发表于 2023-05-04 17:25:54 回复(0)
提交观点

问题信息

动态规划
难度：
72条回答 6771浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号