[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]范围内。
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;
} 
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 两次交易所能获得的最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public int maxProfit (int[] prices) {
int dp[][][] = new int[prices.length][2][2];
// dp[i][j][k] 第i天，所处第j次交易，持有状态为k-0已买入,1已卖出，交易次数j-0,1
// dp[i][0][0] 第i天，1次交易，持有1，买入，已买入1次
// dp[i][0][1] 第i天，1次交易，持有0，卖出，已卖出一次
// dp[i][1][0] 第i天，2次交易，持有1，买入，已买入2次
// dp[i][1][1] 第i天，2次交易，持有0，卖出，已卖出2次
dp[0][0][0]= -1*prices[0];//初始化第一天买入一次
dp[0][1][0]= -1*prices[0];//初始化不可能买入第二次，所以设极小值
for(int i = 1; i< prices.length;i++){
for(int j=0;j<2;j++){
dp[i][j][0]=Math.max((j==0?0:dp[i-1][j-1][1])-prices[i],dp[i-1][j][0]);
dp[i][j][1]=Math.max(dp[i-1][j][0]+prices[i],dp[i-1][j][1]);
}
}
return dp[prices.length-1][1][1];
}
} import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 两次交易所能获得的最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public int maxProfit (int[] prices) {//空间复杂度O(1),时间复杂度O(n)
int firstBuy =-prices[0];// 截止今天，已买入1次
int firstSell =0;// 截止今天，已卖出1次
int secBuy =-prices[0];// 截止今天，已买入2次
int secSell =0;// 截止今天，已卖出2次
int preFirstBuy;//记录上一天中第一次已买入
int preSecBuy;//记录上一天中第二次已买入
for(int i = 1; i< prices.length;i++){
preFirstBuy = firstBuy;
preSecBuy = secBuy;
firstBuy = Math.max(-prices[i],preFirstBuy);
secBuy = Math.max(firstSell-prices[i],secBuy);
firstSell = Math.max(preFirstBuy+prices[i],firstSell);
secSell = Math.max(preSecBuy+prices[i],secSell);
}
return secSell;
}
} 
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 两次交易所能获得的最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public int maxProfit (int[] prices) {
// write code here
//0 1第一次买入 2第一次卖出 3第二次买入 4第二次卖出
if(prices==null||prices.length==1) return 0;
int[][] dp=new int[prices.length][5];
dp[0][0]=0;
dp[0][1]=-prices[0];
dp[0][2]=0;
dp[0][3]=-prices[0];
dp[0][4]=0;
for(int i=1;i<prices.length;i++){
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],dp[prices.length-1][4]);
}
} 
。 
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 两次交易所能获得的最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public static int maxProfit(int[] prices) {
// write code here
int[][] dp = new int[prices.length][4];
for (int i = 0; i < prices.length; i++) {
if (i == 0) {
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = -prices[0];
dp[0][3] = 0;
} else {
dp[i][0] = Math.max(-prices[i], dp[i - 1][0]);
dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
dp[i][2] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][2]);
dp[i][3] = Math.max(dp[i - 1][2] + prices[i], dp[i - 1][3]);
}
}
return dp[prices.length - 1][3];
}
} 
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][2][2];
dp[0][0][0] = 0;
dp[0][0][1] = 0;
dp[0][1][0] = -prices[0];
dp[0][1][1] = -prices[0];
for(int i = 1;i < len; i++){
dp[i][1][0] = Math.max(dp[i - 1][1][0],-prices[i]); //第一次持有
dp[i][0][0] = Math.max(dp[i - 1][1][0]+prices[i],dp[i - 1][0][0]);//第一次没持有
dp[i][1][1] = Math.max(dp[i - 1][0][0]-prices[i],dp[i - 1][1][1]);//第二次持有
dp[i][0][1] = Math.max(dp[i - 1][1][1]+prices[i],dp[i - 1][0][1]);//第二次没持有
}
return dp[len - 1][0][1];
}
} 
public int maxProfit (int[] prices) {
int dp[]=new int[4];
dp[0]=-prices[0];//1th purchase' left on 1th day
dp[1]=0;//1th sell' earn on 1th day
dp[2]=-prices[0];//2th purchase' left on 1th day
dp[3]=0;//2th sell' earn on 1th day
//Comparing with the max price of the previous day and the price of the current day
for(int i=0;i<prices.length;i++){
dp[0]=Math.max(dp[0],-prices[i]);//1th purchase' left on ith day
dp[1]=Math.max(dp[1],prices[i]+dp[0]);//1th sell' earn on ith day
dp[2]=Math.max(dp[2],dp[1]-prices[i]);//2th purchase' left on ith day
dp[3]=Math.max(dp[3],prices[i]+dp[2]);//2th sell' earn on ith day
}
return dp[3];
} 
三次遍历
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 两次交易所能获得的最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public int maxProfit (int[] prices) {
// write code here
int first_max=0;
int second_max=0;
int third_max=0;
int min=prices[0];
int idx_min=0;
int idx_max=0;
//第一次遍历
for(int i=1;i<prices.length;i++){
int num = prices[i]-min;
if(num > first_max){
idx_max = i;
first_max = num;
}
if(prices[i] < min){
idx_min = i;
min = prices[i];
}
}
min = prices[0];
//第二次遍历
for(int i=1;i<=idx_min;i++){
int num = prices[i]-min;
second_max = Math.max(num, second_max);
min = Math.min(min, prices[i]);
}
min = Integer.MAX_VALUE;
//第三次遍历
for(int i=idx_max;i<=prices.length-1;i++){
int num = prices[i]-min;
third_max = Math.max(num, third_max);
min = Math.min(min, prices[i]);
}
return first_max + Math.max(second_max, third_max);
}
} 
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 两次交易所能获得的最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public int maxProfit (int[] prices) {
//按照状态设置变量
int n=prices.length;
if(n==0||n==1) return 0;
//初始化
int fhost=-prices[0];
int fnohost=0;
int shost=-prices[0];
int snohost=0;
for(int i=1;i<n;i++){
fhost=Math.max(fhost,-prices[i]);
fnohost=Math.max(fnohost,fhost+prices[i]);
shost=Math.max(shost,fnohost-prices[i]);
snohost=Math.max(snohost,shost+prices[i]);
}
return snohost>0?snohost:0;
}
}
public int maxProfit (int[] prices) {
if(prices.length == 0) return 0;
int b1 = -prices[0], b2 = -prices[0];
int s1 = 0, s2 = 0;
for(int i = 0; i < prices.length; i++){
b1 = Math.max(b1, -prices[i]);
s1 = Math.max(s1, prices[i] + b1);
b2 = Math.max(b2, s1 - prices[i]);
s2 = Math.max(s2, prices[i] + b2);
}
return s2;
} 
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
// =========================================================
}
}
import java.util.*;
//https://www.bilibili.com/video/BV1To4y1d7TA?from=search&seid=13789178051737712436
public class Solution {
public int maxProfit (int[] prices) {
int[][] dp=new int[prices.length][5];
dp[0][1]=-prices[0];
dp[0][3]=-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 dp[prices.length-1][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];
}
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
