在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于 2 )，规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列，请写一个程序计算一天可以获得的最大收益。请采用时间复杂度低的方法实现。
给定价格序列 prices 及它的长度 n ，请返回最大收益。
数据范围： 
，
[编程题]股票交易日
import java.util.*;
public class Stock {
public int maxProfit(int[] prices, int n) {
// write code here
// 动态规划(易于理解版本)
// 0: 第一次买入
// 1: 第一次卖出
// 2: 第二次买入
// 3: 第二次卖出
int[][] dp = new int[n][4];
// 第一个元素，长度为1，只能执行买入操作。
dp[0][0] = -prices[0];
dp[0][1] = -prices[0];
dp[0][2] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i < n; i++) {
// 在 当前不买入 和 当前买入 取最大
dp[i][0] = Math.max(dp[i - 1][0], -prices[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]);
}
// 最大收益应该大于等于0，因为可以什么也不买不卖
return Math.max(
0,
Math.max(dp[n - 1][1], dp[n - 1][3])
);
}
}
发表于 2022-05-20 13:27:26
回复(0)
import java.util.*;
public class Stock {
public int maxProfit(int[] prices, int n) {
int firstBuy = Integer.MIN_VALUE,firstSell = 0;
int secondBuy = Integer.MIN_VALUE,secondSell = 0;
for (int price : prices) {
firstBuy = Math.max(firstBuy, -price);
firstSell = Math.max(firstSell, firstBuy + price);
secondBuy = Math.max(secondBuy, firstSell - price);
secondSell = Math.max(secondSell, secondBuy+price);
/*firstBuy更新则firstSell不更新,差值大才更新
1.firstBuy比过去买的价格高,无论何时差值一定比过去小,必不买
2.firstBuy比过去买的价格低,firstBuy这轮跟踪,firstSell这轮不变(同secondBuy)
*/
/*secondBuy更新则secondSell不更新,差值大才更新
1.firstSell更新引起的(firstBuy保持不变,secondBuy=max(secondBuy,firstBuy)),
firstBuy一定是最低价格,故secondBuy=firstBuy,比较max(以前secondSell,现在firstSell)
2.price比过去的价格低,secondBuy这轮跟踪,secondSell这轮不变
这里price低只针对的是secondBuy的过去价格,secondBuy与firstBuy起点不同,
firstBuy的价格一定是最低价,最低价 < 这里price < secondBuy的过去价格
*/
}
return secondSell;
}
}
发表于 2021-08-17 10:40:37
回复(0)
/**
以第i天为分界线， 计算 [0, i-1]和[i, n-1]的最大收益，取和最大的
*/
import java.util.*;
public class Stock {
public int maxProfit(int[] prices, int n) {
// write code here
if(n <= 4) return 0;
int res = 0;
for(int i = 2; i < n; i++){
res = Math.max(res, maxProfit(prices, 0, i-1) + maxProfit(prices, i, n-1));
}
return res;
}
public int maxProfit(int[] prices, int start, int end){
if(start >= end) return 0;
int left = start, right = start+1;
int res = Math.max(prices[right] - prices[left], 0);
while(right <= end){
if(prices[right] > prices[left]){
res = Math.max(res, prices[right] - prices[left]);
right++;
}else{
left = right;
right++;
}
}
return res;
}
}
发表于 2021-03-16 19:49:55
回复(0)
import java.util.*;
public class Stock {
public int helper(int[] prices, int n, int x, int y) {
if(x >= y) return 0;
int[] pre = new int[n];
int[] pos = new int[n];
pre[x] = prices[x]; pos[y] = prices[y];
for(int i = x+1; i <= y; i++) pre[i] = Math.min(pre[i-1], prices[i]);
for(int i=y-1; i >= x; i--) pos[i] = Math.max(pos[i+1], prices[i]);
int res = 0;
for(int i=x; i <= y; i++) {
res = Math.max(res, pos[i] - pre[i]);
}
return res;
}
public int maxProfit(int[] prices, int n) {
int res = 0;
for(int i=0; i < n; i++) {
int t = helper(prices, n, 0, i);
t += helper(prices, n, i+1, n-1);
res = Math.max(res, t);
}
return res;
}
}
发表于 2020-07-01 23:06:38
回复(0)
import java.util.*;
public class Stock {
public static int maxProfit(int[] prices, int n) {
int[] leftProfit = new int[prices.length];
int[] rightProfit = new int[prices.length];
int minValue = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; ++i) {
if (prices[i] - minValue > leftProfit[i - 1]) {
leftProfit[i] = prices[i] - minValue;
} else {
leftProfit[i] = leftProfit[i - 1];
}
if (prices[i] < minValue) {
minValue = prices[i];
}
}
int maxValue = prices[prices.length - 1];
for (int i = prices.length - 2; i >= 0; --i) {
if (maxValue - prices[i] > rightProfit[i + 1]) {
rightProfit[i] = maxValue - prices[i];
} else {
rightProfit[i] = rightProfit[i + 1];
}
if (prices[i] > maxValue) {
maxValue = prices[i];
}
}
for (int i = 0; i < prices.length - 1; ++i) {
if (leftProfit[i] + rightProfit[i + 1] > maxProfit)
maxProfit = leftProfit[i] + rightProfit[i + 1];
}
if (leftProfit[leftProfit.length - 1] > maxProfit) {
maxProfit = leftProfit[leftProfit.length - 1];
}
if (rightProfit[0] > maxProfit) {
maxProfit = rightProfit[rightProfit.length - 1];
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices = { 10, 22, 5, 75, 65, 80 };
maxProfit(prices, prices.length);
}
}
发表于 2017-06-22 20:09:19
回复(0)
隔壁题抄来的，这里貌似没有
import java.util.*;
public class Stock {
public int maxProfit(int[] prices, int n) {
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;
for (int curPrice : prices) {
firstBuy = Math.max(firstBuy, -curPrice);
firstSell = Math.max(firstSell, firstBuy + curPrice);
secondBuy = Math.max(secondBuy,firstSell - curPrice);
secondSell = Math.max(secondSell, secondBuy + curPrice);
}
return secondSell;
}
}
发表于 2017-02-21 16:40:17
回复(1)
import java.util.*;
public class Stock {
public int maxProfit(int[] prices, int n) {
int dp[] = new int[n];
int max = 0;
for (int i = 0; i < dp.length; i ++ )
dp[i] = getProfit(prices, 0, i) + getProfit(prices, i, n - 1);
for (int i = 0; i < dp.length; i ++ )
max = max > dp[i] ? max : dp[i];
return max;
}
public static int getProfit(int[] prices, int start, int end) {
int profit = 0;
for (int i = start; i <= end; i ++ )
for (int j = i + 1; j <= end; j ++ )
profit = profit > prices[j] - prices[i] ? profit : prices[j] - prices[i];
return profit;
}
}
编辑于 2016-09-10 00:18:02
回复(0)
import java.util.*;
//已通过测试，发现好多人都不喜欢写注释，喜欢直接粘代码，
public class Stock {
//简单说一下我的做题思路，
//其实我的原始思路是用二分法做，先把数组从中间分开，
//然后在两部分中分别找最大差值，然后保存最大差值进行相加
//完事之后，将中间的指针，也就是进行二分的指针向右移或者向左移
//又划分成了两部分，依次找最大差值，
//直到最后两个差值之和为最大值，返回最大值。
public int maxProfit(int[] prices, int n) {
int temp1 = 0,temp2 = 0 , temp3 = 0, l = 0;
//既然从中间划分两部分，之后又要在往前划分和往后划分，
//所以直接一开始就从最前面开始划分，将数组划分两部分
while(l<n){
//l变量用来划分数组
//第一个for循环寻找的最大差值，仅限于l变量之前。
for(int i = 0 ; i < l+1 ; i++){
for(int j = i+1 ; j < l+1 ; j++){
if(prices[j]-prices[i]>temp1){
temp1 = prices[j]-prices[i];
}
}
}
//第二个for循环寻找的最大差值，仅限于l变量之后。
for(int i = l+1 ; i < n ; i++){
for(int j = i+1 ; j < n ; j++){
if(prices[j]-prices[i]>temp2){
temp2 = prices[j]-prices[i];
}
}
}
//判断两个变量之和是否是最大差值
if(temp2+temp1>temp3){
temp3 = temp2+temp1 ;
}
//此处一定要将两个部分的最大差值重新置0；
//否则结果会出错。因为它里面存有之前的最大差值
//如果不重置，那么最后在判断的时候会重复计算。
temp2 = 0 ;
temp1 = 0;
l++;
}
return temp3;
}
}
编辑于 2016-09-09 10:40:50
回复(10)
用野办法，总的来说，就是运用每天：
1.将价格数，后一个数值减去前一个数值，得到每天的利润数组；
2.将价格数的后一天减去前一天，得到每天的利润的负数数组；
3.从利润数组头开始，计算到每一天的最大利润值，得到数组A；
4.从负利润数组尾开始，计算到前面每一天的最小值，得到数组B；
5.利用A-B，求对应的最大值；
import java.util.*;
public class Stock {
public int[] getMax(int[] dis, int n) {
int[] dp = new int[n];
int max = Integer.MIN_VALUE;
int current = 0;
for (int i = 0; i < dis.length; ++i) {
current += dis[i];
current = Math.max(current, dis[i]);
max = Math.max(current, max);
dp[i] = max;
}
return dp;
}
public int[] getMin(int[] dis, int n) {
int[] dp = new int[n];
int min = Integer.MAX_VALUE;
int current = 0;
for (int i = dis.length - 1; i >= 0; --i) {
current += dis[i];
current = Math.min(current, dis[i]);
min = Math.min(current, min);
dp[i] = min;
}
return dp;
}
public int maxProfit(int[] prices, int n) {
// write code here
int[] dis = new int[prices.length];
int[] dis2 = new int[prices.length];
for (int i = 1; i < dis.length; ++i) {
dis[i] = prices[i] - prices[i - 1];
}
for (int i = dis.length - 2; i >= 0; --i) {
dis2[i] = prices[i] - prices[i + 1];
}
int[] max = getMax(dis, n);
int[] min = getMin(dis2, n);
int result = Integer.MIN_VALUE;
for (int i = 0; i < max.length; ++i) {
result = Math.max(result, max[i] - min[i]);
}
return result;
}
}
编辑于 2016-08-26 16:52:36
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-15 21:25:49 -
2022-09-11 15:10:38 -
2022-09-10 23:47:30
-
2022-09-10 14:35:05
-
2022-09-08 18:11:13
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
