[8,9,3,5,1,3]
4
第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2 第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2 总收益为4。
[9,8,4,1]
0
[1,2,8,3,8]
12
第一笔股票交易在第一天买进，第三天卖出；第二笔股票交易在第四天买进，第五天卖出；总收益为12。 因最多只可以同时持有一只股票，所以不能在第一天进行第一笔股票交易的买进操作，又在第二天进行第二笔股票交易的买进操作（此时第一笔股票交易还没卖出），最后两笔股票交易同时在第三天卖出，也即以上操作不满足题目要求。
总天数不大于200000。保证股票每一天的价格在[1,100]范围内。
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
// =========================================================
}
}
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;
} 
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];
}
} 到第i天为止的5种状态：
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) 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
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);
}
}; 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有个问题，如果是三次买入卖出，还有讨巧的余地吗？
#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;
}
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]));
}
}; # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 两次交易所能获得的最大收益 # @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)
class Solution: def maxProfit(self , prices: list[int]) -> int: first = max(prices)-min(prices) prices.remove(max(prices)) prices.remove(min(prices)) secend = max(prices)-min(prices) return first + secend
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));
}
} 
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));
}
}
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
}
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));
}
}; 
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;
}
} 
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;
} 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])
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
