首页 > 试题广场 >

股票交易日

[编程题]股票交易日
  • 热度指数:8569 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

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

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

数据范围:
示例1

输入

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

输出

87

如果只能买卖一次相信大家都会做
用左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)
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)
//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)
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)
用野办法,总的来说,就是运用每天:
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)
classStock {
public:
    intmaxProfit(vector<int> prices,intn) {
        // write code here
        intmax=0;
        intp[n][n];
        for(inti=0;i<n;i++)
            for(intj=0;j<n;j++)
            p[i][j]=0;
             
        for(inti=0;i<n-1;i++)
            for(intj=i+1;j<n;j++)
          {
            p[i][j]=prices[j]-prices[i];
            if(p[i][j]>max)                  //一次买卖中最大收益
            max=p[i][j];
          }
             
        for(inti=0;i<n-3;i++)
            for(intj=i+1;j<n-2;j++)
            {
              for(intx=j+1;x<n-1;x++)
                for(inty=x+1;y<n;y++)
                 if(p[i][j]+p[x][y]>max)     //最多两次买卖的最大收益
                  max=p[i][j]+p[x][y];
           }
   
      returnmax;
    }
};
发表于 2015-10-23 10:19:51 回复(4)
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)

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)
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)

此题略坑啊

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)
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)
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)
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)
        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)
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)
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)
//哈哈,这是我以前做过的题目。。。。复杂度最低的算法:
    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)

热门推荐

通过挑战的用户

查看代码