首页 > 试题广场 >

股票交易日

[编程题]股票交易日

热度指数：8692 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于 2 )，规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列，请写一个程序计算一天可以获得的最大收益。请采用时间复杂度低的方法实现。

给定价格序列 prices 及它的长度 n ，请返回最大收益。

数据范围： $1 \le n \le 500 \$ ， $1 \le prices_i \le 1000 \$

示例1

输入

[10,22,5,75,65,80],6

输出

算法知识视频讲解

ZhanHeng

import java.util.*;

public class Stock {
    //分别得出以i点为分割点，左半段最大收益的数组left，和右半段最大收益的数组right后.
    //我们就可以遍历一遍这两个数组，找出最大的left+right组合。
    public int maxProfit(int[] prices, int n) {
        if (n==0){ return 0; }
        int[] left = new int[n];
        int[] right= new int[n];
        int leftMin=prices[0];
        int rightMax=prices[n-1];
        int sum = 0;
        //prices[0]到prices[i]的最大收益应该:
        // 当前卖出能获得的最大收益 和 prices[0]到prices[i-1]的最大收益中
        // 二者较大的那个。
        for(int i = 1 ; i<n ; i++){
           leftMin = Math.min(prices[i],leftMin);
           left[i] = Math.max(prices[i]-leftMin , left[i-1]);
        }
        for(int i = n-2 ; i>=0 ;i--){
            rightMax = Math.max(prices[i],rightMax);
            right[i] = Math.max(rightMax-prices[i] , right[i+1]);
        }
        for(int i = 0 ;i<n ;i++){
             if((left[i]+right[i])>sum) sum = left[i]+right[i];
        }
        return sum;
    }
}

发表于 2016-07-06 12:11:20 回复(3)

Shield_W

//time complexiy O(n), space complexity O(n)
public class Stock {
    public int maxProfit(int[] prices, int n) {
        // write code here
        if (n == 0) {
            return 0;
        }
        //from left to right
        int[] profitBefore = new int[n];
        int buyMin = prices[0];
        profitBefore[0] = 0;
        for (int i = 1; i < n; i++) {
            buyMin = Math.min(buyMin, prices[i]);
            profitBefore[i] = Math.max(profitBefore[i - 1], prices[i] - buyMin);
        }
        //from right to left
        int[] profitAfter = new int[n];
        int sellMax = prices[n - 1];
        profitAfter[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            sellMax = Math.max(sellMax, prices[i]);
            profitAfter[i] = Math.max(profitAfter[i + 1], sellMax - prices[i]);
        }
        //combine
        int max = 0;
        for (int i = 0; i < n - 1; i++) {
            max = Math.max(max, profitBefore[i] + profitAfter[i]);
        }
        return max;
    }
}

编辑于 2016-03-11 15:11:16 回复(2)

请继续，○◇

Leetcode 第123题

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/

发表于 2018-04-23 17:39:59 回复(0)

Alex-大伟

public int maxProfit(int[] prices, int n) {
		//第i天之前的最大收益
		int[] preMaxProfit = new int[n];
		//第i天之后的最大收益
		int[] postMaxProfit = new int[n];
		//总的最大收益
		int maxProfit = Integer.MIN_VALUE;
		//如果今天的价格减掉最小价格比截止到昨天的最大收益大，
		//就用今天的价格减去最小的价格；否则，用截止到昨天的最大收益
		int minBuy = prices[0];
		for(int i=1;i<n;i++){
			minBuy = Math.min(minBuy, prices[i]);
			preMaxProfit[i] = Math.max(preMaxProfit[i-1], prices[i] - minBuy);
		}
		//如果最大价格减掉今天价格比明天以后买入的最大收益大，
		//就用最大价格减掉今天的价格；否则，用明天以后买入的最大收益 
		int maxSell = prices[n-1];
		for(int i=n-2;i>=0;i--){
			maxSell = Math.max(maxSell, prices[i]);
			postMaxProfit[i] = Math.max(postMaxProfit[i+1], maxSell - prices[i]);
		}
		 //总的最大利润 
		for(int i=0;i<n;i++){
			maxProfit = Math.max(maxProfit, preMaxProfit[i]+postMaxProfit[i]);
		}
		return maxProfit;
    }

编辑于 2016-09-08 22:55:24 回复(1)

Java

JustYoung

用野办法，总的来说，就是运用每天：

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)

老石基

import java.util.*;

public class Stock {
    public int maxProfit(int[] prices, int n) {
        // write code here
        int[] left = new int[n];
        int[] right = new int[n];
        int min = prices[0];
        int cost = 0;
        for(int i = 1;i<prices.length;i++){
            if(prices[i]-min>cost){
                cost = prices[i]-min;
            }
            if(prices[i]<min)
                min = prices[i];
            left[i] = cost;
        }
        cost = 0;
        int max = prices[n-1];
        for(int i = n-1;i>=0;i--){
        	if(max-prices[i]>cost){
                cost = max-prices[i];
            }
            if(prices[i]>max)
                max = prices[i];
            right[i] = cost;
        }
        int r = 0;
        for(int i = 1;i<n-1;i++)
        	if(left[i]+right[i]>r)
        		r = left[i]+right[i];
        return r;
    }
}

发表于 2016-04-14 16:59:41 回复(0)

钓鱼人

importjava.util.*;

publicclassStock {

publicintmaxProfit(int[] prices, intn) {

intmax=0;

for(inti=0;i<prices.length;i++) {

for(intj=i+1;j<prices.length;j++) {

intsum=prices[j]-prices[i];

max=Math.max(max, sum);

for(intk=j+1;k<prices.length;k++) {

for(intt=k+1;t<prices.length;t++){

inttum=prices[t]-prices[k];

max=(int)Math.max(max, sum+tum);

}

returnmax;

}

发表于 2019-07-06 20:31:27 回复(0)

Python

华科平凡

leetcode上的原题，python解法如下

class Stock:
    def maxProfit(self, prices, n):
        if not prices: return 0
        left, right = [], []
        minLeft, cur = prices[0], 0
        for i, v in enumerate(prices):
            cur = max(v - minLeft, cur)
            left.append(cur)
            minLeft = min(minLeft, v)
        maxRight, cur = prices[-1], 0
        for i, v in enumerate(prices[::-1]):
            cur = max(maxRight - v, cur)
            right.insert(0, cur)
            maxRight = max(maxRight, v)
        return max(map(lambda c: left[c] + right[c], range(len(prices))))

更简单的解法：

class Stock:
    def maxProfit(self, prices, n):
        buy1, buy2, sell1, sell2 = -999999999, -9999999999, 0, 0
        for x in prices:
            sell2 = max(sell2, buy2 + x)
            buy2 = max(buy2, sell1 - x)
            sell1 = max(sell1, buy1 + x)
            buy1 = max(buy1, -x)
        return sell2

两种解法都测试通过。。时间复杂度均为O(n)

发表于 2017-11-07 17:58:11 回复(1)

C/C++

nbgao

class Stock {
public:
    int maxProfit(vector<int> prices, int n) {
        if(n==0) 
            return 0;
        vector<int> profit1(n,0);
        vector<int> profit2(n,0);
        int Min = prices[0];
        int Max = prices[n-1];
        int MaxProfit = 0;
        
        for(int i=1;i<n;i++)
        {
            Min = min(prices[i], Min);
            profit1[i] = max(profit1[i-1], prices[i]-Min);         }
        for(int i=n-2;i>=0;i--)
        {
            Max = max(prices[i], Max);
            profit2[i] = max(profit2[i+1], Max-prices[i]);         }         for(int i=0;i<n;i++)             MaxProfit = max(MaxProfit, profit1[i]+profit2[i]);         return MaxProfit;
    }
};

发表于 2017-10-17 00:49:55 回复(0)

HelloWorldn

此题略坑啊

public int maxProfit(int[] prices, int n) {
        int len = n;
        int res = maxProfitHelp(prices, 0, len - 1);
        for (int i = 2; i <= len - 2; i++) {
            int valLeft = maxProfitHelp(prices, 0, i - 1);
            int valRight = maxProfitHelp(prices, i, len - 1);
            int val = valLeft + valRight;
            if (valLeft > res) res = valLeft;
            if (valRight > res) res = valRight;
            if (val > res) res = val;
        }
        return res;
    }

    private int maxProfitHelp(int[] prices, int left, int right) {
        int min = prices[left];
        int max = prices[left + 1];
        int res = max - min;

        if(max < min){
            min = max;//十分隐蔽的bug
        }
        for (int i = left + 2; i <= right; i++) {
            if (prices[i] < min) {
                min = prices[i];
                max = Integer.MIN_VALUE;
            } else {
                if (prices[i] > max) {
                    max = prices[i];
                    res = Math.max(res, max - min);
                }
            }
        }
        return res;
    }

发表于 2017-02-08 21:26:21 回复(0)

fight灬奋斗

class Stock {
public:
    int maxProfit(vector<int> prices, int n) {
        if(n<4)
            return 0;
        vector<int> vec(n,0);
        int min=prices[0];
        for(int i=1;i<n;i++){
            if(prices[i]-min<=vec[i-1]){
            	vec[i]=vec[i-1];
        	}else{
            	vec[i]=prices[i]-min;
        	}
            if(prices[i]<min)
                min=prices[i];
        }
        int max=prices[n-1];
        int R=0;
        for(int i=n-2;i>0;i--){
            if(max-prices[i]+vec[i-1]>R)
            	R=max-prices[i]+vec[i-1];
            if(prices[i]>max)
            	max=prices[i];
        }
        return R;
    }
};

发表于 2016-09-07 15:31:11 回复(0)

会呼吸旳痛

//DP 
//forward(n)表示第一次交易第n天卖出最大获利
//backward(n)表示第二次交易第n天买入最大获利
class Stock {
public:
    int maxProfit(vector<int> prices, int n) {
        // write code here        
        vector<int> forward(n,0);
        int minV = prices[0];
        forward[0]=0;
        
        for(int i=1;i<n;i++)
        {
            if(prices[i]<minV)minV=prices[i];
            forward[i] = max(prices[i]-minV,forward[i-1]);
        }
        
        vector<int>backward(n,0);
        int maxV = prices[n-1];
        backward[n-1]=0;
        for(int j=n-2;j>=0;j--)
        {
           if(prices[j]>maxV)maxV=prices[j];
           backward[j] = max(maxV-prices[j],backward[j+1]);
        }
        
        int ans = numeric_limits<int>::min();
        for(int i=1;i<n-2;i++)
            ans = max(forward[i]+backward[i+1],ans);
        ans = max(max(ans,forward[n-1]),backward[0]); //可能只有一次操作
       return ans;    
    }
};

发表于 2016-08-25 16:33:12 回复(0)

OnePiece~~

class Stock {
public:
  int getMin(vector<int> prices,int begin,int end){
        vector<int> dp(end-begin+1);
        dp[0]=-prices[begin+0];
        dp[1]=prices[begin+1]-prices[begin+0];
        int pof=dp[1]+prices[begin+1]>0? dp[1]:-prices[begin+1];
        int min=prices[begin+0]>prices[begin+1]? prices[begin+1]:prices[begin+0];
        for(int i=begin+2;i<=end;i++){
            dp[i-begin]=prices[i]-min;
            if(pof<dp[i-begin])
                pof=dp[i-begin];
            if(prices[i]<min)
                min=prices[i];
        }
        return pof;
    }
	int maxProfit(vector<int> prices, int n) {
        /*时间复杂度为O(n*n)*/
        int max=getMin(prices,0,n-1);
        for(int i=1;i<n-2;i++){
           int p=getMin(prices,0,i)+getMin(prices,i+1,n-1);
           if(p>max){
               max=p;
           } 
        }
        return max;
    }
};

发表于 2016-08-14 13:21:52 回复(0)

tmp11290

int maxProfit(vector<int> prices, int n) {
        // write code here
        int minPrice = prices[0];
        vector<int> max_profit1(n, 0);
        for(int i = 1; i < n; ++i){
            max_profit1[i] = std::max(max_profit1[i-1], prices[i]-minPrice);
            minPrice = std::min(minPrice, prices[i]);
        }
        int maxPrice = prices[n-1];
        vector<int> max_profit2(n, 0);
        for(int i = n-2; i >= 0; --i){
            max_profit2[i] = std::max(max_profit2[i+1], maxPrice-prices[i]);
            maxPrice = std::max(maxPrice, prices[i]);
        }
        for(int i = 0; i < n; ++i)
            max_profit1[i] += max_profit2[i];
        return *max_element(max_profit1.begin(), max_profit1.end());
    }

发表于 2016-03-07 19:00:48 回复(0)

hellowword

int maxProfit(vector<int> prices, int n) {

// write code here

int maxp1 = 0;

int maxp2 =0;

int maxp3 =0;

vector<int> *G = new vector<int>[n-1];

int x,y;

for(int i=0;i<n;i++){

for(int j = i+1;j<n;j++){

G[i].push_back(prices[j]-prices[i]);

}

for(int i=0;i<n-1;i++){

int m = G[i].size();

for(int j =0;j<m;j++){

if(G[i][j]>maxp1){

maxp1 = G[i][j];

x = i;

y = i+j+1;

}

int temp1,temp2,k;

temp1 =0;

temp2 =0;

for(int j=x+1;j<y;j++){

if(prices[j]-prices[x] > temp1){

temp1 = prices[j]-prices[x];

k = j;

}

k = k+1;

for(int i = k;i<y;i++){

for(int j=i+1;j<=y;j++){

temp2 = max(temp2,prices[j]-prices[i]);

}

delete[] G;

x = x-1;

y = y+1;

if(x == 0){

maxp2 = 0;

}

else{

vector<int> G1;

for(int i=0;i<x;i++){

for(int j = i+1;j<=x;j++){

G1.push_back(prices[j]-prices[i]) ;

}

for(int i=0;i<G1.size();i++){

if(G1[i]>maxp2){

maxp2 = G1[i];

}

G1.clear();

}

if(y == n-1){

maxp3 = 0;

}

else {

vector<int> G2;

for(int i=y;i<n;i++){

for(int j = i+1;j<n;j++){

G2.push_back(prices[j]-prices[i]) ;

}

for(int i=0;i<G2.size();i++){

if(G2[i]>maxp3){

maxp3 = G2[i];

}

maxp1 = maxp1+max(maxp2,maxp3);

maxp1 = max(maxp1,temp1+temp2);

return maxp1;

}

发表于 2015-10-23 17:53:15 回复(0)

selfboot

class Stock {
public:
    int maxProfit(vector<int> prices, int n) {
        // write code here
        if (n==0){
            return 0;
        }
        vector<int> pre_profit(n,0);
        vector<int> post_profit(n,0);

        int min_buy = prices[0];
        for(int i=1;i<n;i++){
            min_buy = min(prices[i], min_buy);
            pre_profit[i] =  max(pre_profit[i-1], prices[i]-min_buy);
        }

        int max_sell = prices[n-1];
        for(int j=n-2;j>=0;j--){
            max_sell = max(prices[j], max_sell);
            post_profit[j] = max(post_profit[j+1], max_sell-prices[j]);
        }

        int max_profit = 0;
        for(int i=0; i<n;i++){
            max_profit = max(max_profit, pre_profit[i] + post_profit[i]);
        }
        return max_profit;
    }
};

动态规划法。以第i天为分界线，计算第i天之前进行一次交易的最大收益preProfit[i]，和第i天之后进行一次交易的最大收益postProfit[i]，最后遍历一遍，max{preProfit[i] + postProfit[i]} (0≤i≤n-1)就是最大收益。

发表于 2016-03-09 14:04:27 回复(12)

Java

南山北

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)

trytrytry66

//哈哈，这是我以前做过的题目。。。。复杂度最低的算法：

    public static int maxProfit(int[] prices, int n) {
    	int firstBuyProfit=Integer.MIN_VALUE;
    	int firstSaleProfit=Integer.MIN_VALUE;
    	int secondBuyProfit=Integer.MIN_VALUE;
    	int secondSaleProfit=Integer.MIN_VALUE;
    	for (int i = 0; i < n; i++) {
			firstBuyProfit=Math.max(firstBuyProfit, -prices[i]);
			firstSaleProfit=Math.max(firstSaleProfit, firstBuyProfit+prices[i]);
			secondBuyProfit=Math.max(secondBuyProfit, firstSaleProfit-prices[i]);
			secondSaleProfit=Math.max(secondSaleProfit, secondBuyProfit+prices[i]);
		}
    	return secondSaleProfit;
    }

编辑于 2017-05-30 09:31:06 回复(9)

C/C++

卷积神经网络哦

如果只能买卖一次相信大家都会做
用左l 右r 两个下标滑动可以在O(n)时间内完成
见函数Once 不多解释了
但是要购买两次这就有点麻烦不过题目说了必须两次分开所以必须是买卖买卖的顺序这样就可以用二分的思想
将区间分为长度大于2的左右两个区间共n-3总分法每一种分法两边区间各调用一次Once函数然后求和即可

class Stock {
public:
    int Once(vector<int> Prices, int left, int right){
        int l = left, r = left + 1;
        int ans = 0;
        while(r <= right){
            if(Prices[r] > Prices[l]) ans = max(ans, Prices[r] - Prices[l]);
            else l = r;
            r++;
        }
        return ans;
    }

    int maxProfit(vector<int> prices, int n) {
        int max_ans = Once(prices, 0, n-1);
        if(n >= 4){
            for(int i = 1; i <= n - 3; i++){
                int tmp = Once(prices, 0, i) + Once(prices, i+1, n-1);
                max_ans = max(tmp, max_ans);
            }
        }
        return max_ans;
    }
};

编辑于 2018-10-18 19:44:54 回复(1)

C/C++

cycleof

/*这才是复杂度最低的算法，好多人参考lc上答案，其实并没有理解精髓。
核心的四个句子不是并列关系，而是两两互斥，只可能发生其一。
因为较于前一天，股票只可能是跌或者涨，而跌肯定是看能否更低抄底，涨肯定是看此刻出手是否收益更大。不用全看，因此用 if ，else if 复杂度更低，且便于理解。*/  
class Stock {
public:
    int maxProfit(vector<int> prices, int n) {
        int fbegin=INT_MAX,fend=0,sbegin=-INT_MAX,send=0;
        for(int i = 0;i<n;i++){
            if( prices[i] < fbegin )//股票竟然跌了，应该此时买
                fbegin = prices[i];
            else if( prices[i] - fbegin > fend )//股票涨了？要不要卖了，看看收益能否增加
                fend = prices[i] - fbegin;
            if( fend - prices[i] > sbegin )//挣了点钱，瞅准时机,找个机会抄底，再搞一次
                sbegin = fend - prices[i];
            else if( prices[i] + sbegin > send )//又涨了。
                send = prices[i] + sbegin;
        }
        return send;
    }
};
//好理解的算法，计算所有位置的划分后的结果，比较得出最大。
class Stock {
public:
    int max(vector<int> prices,int a,int b){
        int i,j,maxx=0,min = INT_MAX;
        for(i=a;i<b;i++){
            if(prices[i]<min)
                min = prices[i];
            else if(prices[i] - min > maxx)
                maxx = prices[i] - min;
        }
        return maxx;
    }
    int maxProfit(vector<int> prices, int n) {
        int max1,max2,maxxx=0;
        for(int i=0;i<n-1;i++){
            max1 = max(prices,0,i);
            max2 = max(prices,i,n);
            if(max1 + max2 > maxxx)
                maxxx = max1 + max2;
        }
        return maxxx;
    }
};

编辑于 2017-07-24 12:55:14 回复(1)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师 c#工程师 2016 动态规划美团穷举测试开发工程师大数据开发工程师 Java工程师

来自：美团2016研发工程师...

难度：

70条回答 150收藏 28548浏览

通过挑战的用户

查看代码

牛客13061...

2022-09-15 21:25:49
刘黄乐

2022-09-11 15:10:38
牛客33341...

2022-09-10 23:47:30
牛客74411...

2022-09-10 14:35:05
LibraXiong

2022-09-08 18:11:13

股票交易日

输入

输出

leetcode上的原题，python解法如下

更简单的解法：

两种解法都测试通过。。时间复杂度均为O(n)

此题略坑啊

问题信息

热门推荐

通过挑战的用户

相关试题

股票交易日

输入

输出

leetcode上的原题 ，python解法如下

更简单的解法 ：

两种解法都测试通过。。时间复杂度均为O(n)

此题略坑啊

问题信息

热门推荐

通过挑战的用户

相关试题

leetcode上的原题，python解法如下

更简单的解法：