首页 > 试题广场 >

买卖股票的最好时机 iii

[编程题]买卖股票的最好时机 iii

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

假设你有一个数组，其中第i个元素是某只股票在第i天的价格。
设计一个算法来求最大的利润。你最多可以进行两次交易。
注意:
你不能同时进行多个交易(即，你必须在再次购买之前出售之前买的股票)。

示例1

输入

[1,4,2]

输出

示例2

输入

[2,4,1]

输出

算法知识视频讲解

Java

AriesLi

class Solution {
    /**
     *  延续之前的转移方程，假设第i天持有为1，空仓为0
     *  不一样的是因为限定交易次数，还要加一个参数k
     *  第i天第k次交易的持有收益是f(i,k,1), 空仓收益是f(i,k,0)
     *  有：
     *      f(i,k,0) = max(f(i-1,k,0), f(i-1,k,1)+prices[i])
     *      f(i,k,1) = max(f(i-1,k,1), f(i-1,k-1,0)-prices[i])
     *  这样顺带下一题也搞定了
     */
     
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int k1j0 = 0, k1j1 = -prices[0], k2j0 = 0, k2j1 = -prices[0];
        for(int i=1; i<prices.length; i++){
            k2j0 = Math.max(k2j0, k2j1+prices[i]);
            k2j1 = Math.max(k2j1, k1j0-prices[i]);
            k1j0 = Math.max(k1j0, k1j1+prices[i]);
            k1j1 = Math.max(k1j1, 0-prices[i]);
        }
        return k2j0;
    }
}

发表于 2020-01-08 16:44:57 回复(0)

Java

_Done

//结合分治的思维并结合在线处理的算法去求得子区间最大利润：

public class Solution {

    public int maxProfit(int[] prices) {

        int maxprofit = 0;
        if (prices.length < 2) {     //区间长度小于2返回0.
            return 0;
        }
        if (prices.length == 2) {   //区间长度为2
            return Math.max(maxprofit, prices[1] - prices[0]);
        }
        //区间长度大于等于3，采取分治的思想，分为两个子区间。分别求解子区间内的最大利润
        for (int i = 1; i <= prices.length - 2; i++) {
            maxprofit = Math.max(maxprofit,(maxProfitcore(prices, 0, i) + maxProfitcore(prices, i, prices.length - 1)));
        }
        return maxprofit;
    }
    //在线处理求该区间的最大利润
    public int maxProfitcore(int[] prices, int left, int right) {
        int profit = 0;
        int i = left;
        for (int j = left + 1; j <= right; j++) {
            if (prices[j] - prices[i] > 0) {
                int temp = prices[j] - prices[i];
                profit = Math.max(temp, profit);
            }else {
                i = j;
            }
        }
        return profit;
    }
}

发表于 2019-02-23 14:23:57 回复(1)

Java

zhlovy

*抓住一点，无论买还是卖，都要“赚”最多 ，所谓赚最多，就是花的少，卖的多

public class Solution {

public int maxProfit(int[] prices) {

if(prices.length == 0 )

return 0;

int buy1=Integer.MIN_VALUE;

int sell1=0;

int buy2 =Integer.MIN_VALUE;

int sell2 =0;

for(int i=0; i<prices.length ;i++){ //计算每次操作后赚钱最多

buy1 = Math.max(-prices[i],buy1); //第一次买后因为是花钱，所以赚了 -prices[i]元

//要选出花钱最少的那天买

sell1 = Math.max(sell1,buy1 + prices[i]); //第一次卖后赚的钱

buy2 = Math.max(buy2,sell1 - prices[i]); //第二次买，买后赚的钱数为第一次赚的 - 第二次买花的

sell2 = Math.max(sell2,buy2 + prices[i]);// 同第一次卖

}

return sell2;

}

发表于 2017-08-15 10:55:24 回复(2)

Java

萨仁朝格图（大家去脉脉沟通）

public class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE, sell1 = 0, buy2 = Integer.MIN_VALUE, sell2 = 0;
        for(int i = 0; i < prices.length; i++) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
}

发表于 2017-08-14 20:04:46 回复(0)

Java

pp11

    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1)
            return 0;
        int len = prices.length;
        int[] leftMaxProfit = new int[len];
        int[] rightMaxProfit = new int[len];
        // left
        int leftMinIndex = 0;
        for (int i = 0; i < len; ++i) {
            if (i == 0) {
                leftMaxProfit[i] = 0;
                leftMinIndex = 0;
                continue;
            }
            if (prices[i] - prices[i - 1] > 0) {
                leftMaxProfit[i] = Math.max(prices[i] - prices[leftMinIndex], leftMaxProfit[i - 1]);
            } else {
                if (prices[i] < prices[leftMinIndex]) {
                    leftMinIndex = i;
                    leftMaxProfit[i] = leftMaxProfit[i - 1];
                } else {
                    leftMaxProfit[i] = leftMaxProfit[i - 1];
                }
            }
        }
        // right
        int rightMaxIndex = 0;
        for (int j = len - 1; j >= 0; --j) {
            if (j == len - 1) {
                rightMaxIndex = j;
                rightMaxProfit[j] = 0;
                continue;
            }
            if (prices[j + 1] - prices[j] > 0) {
                rightMaxProfit[j] = Math.max(prices[rightMaxIndex] - prices[j], rightMaxProfit[j + 1]);
            } else {
                if (prices[j] > prices[rightMaxIndex]) {
                    rightMaxIndex = j;
                    rightMaxProfit[j] = rightMaxProfit[j + 1];
                } else {
                    rightMaxProfit[j] = rightMaxProfit[j + 1];
                }
            }
        }
        int maxProfit = 0;
        int temp = 0;
        // split
        for (int i = 0; i < len; ++i) {
            temp = leftMaxProfit[i] + rightMaxProfit[i];
            if (temp > maxProfit)
                maxProfit = temp;
        }
        return maxProfit;
    }

发表于 2017-07-30 16:55:13 回复(0)

Java

丫丁

 /**
     * 分别计算出i之前和之后的最大利润pre[i],post[i]
     * 再以i为分割求出两次交易的最大利润（在i处可能卖出再买入，相当于就一次交易）
     * 空间换时间，时间复杂度O(n)，空间复杂度O(n)
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length<2) return 0;
        int[]pre=new int[prices.length];
        int []post=new int[prices.length];
        int min=prices[0];
        for(int i=1;i<prices.length;i++){
            min=Math.min(min,prices[i]);
            pre[i]=Math.max(pre[i-1],prices[i]-min);
        }
        int max=prices[prices.length-1];
        for(int i=prices.length-2;i>=0;i--){
            max=Math.max(max,prices[i]);
            post[i]=Math.max(post[i+1],max-prices[i]);
        }
        int maxProfit=0;
        for(int i=0;i<prices.length;i++){
            maxProfit=Math.max(maxProfit,pre[i]+post[i]);
        }
        return  maxProfit;
    }

发表于 2017-07-17 11:46:59 回复(2)

Java

Holiday_12138

import java.util.*;
public class Solution {
    public int maxProfit(int[] prices) {
        int fb=Integer.MIN_VALUE,sb=Integer.MIN_VALUE,fs=0,ss=0;
        for(int i:prices){
            fb=Math.max(fb,-i);
            fs=Math.max(fs,fb+i);
            sb=Math.max(sb,fs-i);
            ss=Math.max(ss,sb+i);
        }
        return ss;
    }
}

发表于 2017-05-23 15:25:25 回复(0)

Java

詆調壹點

public class Solution {
    public int maxProfit(int[] prices) {
		return Math.max(once(0, prices.length - 1, prices), twice(prices));
	}
	public int once(int start, int end, int[] prices) {
		int max = 0;
		for (int i = start; i <= end; i ++) {
			int sell = 0;
			for (int j = i; j <= end; j ++) {
				sell = sell > prices[j] ? sell : prices[j];
			}
			max = max > sell - prices[i] ? max : sell - prices[i];
		}
		return max;
	}
	public int twice(int[] prices) {
		int max = 0;
		for (int i = 0; i < prices.length; i ++) {
			int sell = once(0, i, prices) + once(i, prices.length - 1, prices);
			max = max > sell ? max : sell;
		}
		return max;
	}
}

发表于 2017-03-19 21:20:00 回复(0)

Java

城市里的养猫者

public class Solution { public int maxProfit(int[] prices) { int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE; int release1 = 0, release2 = 0; for(int i:prices){ // Assume we only have 0 money at first release2 = Math.max(release2, hold2+i); // The maximum if we've just sold 2nd stock so far. hold2    = Math.max(hold2,    release1-i); // The maximum if we've just buy  2nd stock so far. release1 = Math.max(release1, hold1+i); // The maximum if we've just sold 1nd stock so far. hold1    = Math.max(hold1,    -i); // The maximum if we've just buy  1st stock so far.  } return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1. }
}

发表于 2017-03-11 23:20:27 回复(0)

Java

Silvestris

public int maxProfit(int[] prices) { int result = 0; if(prices == null || prices.length < 2){ return 0;
    } if(prices.length == 2){ return prices[1] - prices[0] > 0 ? prices[1] - prices[0] : 0;
    } if(prices.length == 3){
        result = prices[2] - prices[0] > result ? prices[2] - prices[0] : result;
        result = prices[1] - prices[0] > result ? prices[1] - prices[0] : result;
        result = prices[2] - prices[1] > result ? prices[2] - prices[1] : result; return result;
    } int[] dp = new int[prices.length]; int maxPrice = prices[prices.length - 1]; for(int i = prices.length - 2; i >= 0; --i){ int temp = maxPrice - prices[i];
        dp[i] = temp > dp[i + 1] ? temp : dp[i + 1];
        maxPrice = maxPrice > prices[i] ? maxPrice : prices[i];
        result = result > dp[i] ? result : dp[i];
    } int minPrice = prices[0]; int maxProfit = 0; for(int i = 1; i < prices.length - 1; ++i){ int temp = prices[i] - minPrice;
        maxProfit = maxProfit > temp ? maxProfit : temp;
        minPrice = minPrice < prices[i] ? minPrice : prices[i];
        result = result > maxProfit ? result : maxProfit;
        result = result > maxProfit + dp[i + 1] ? result : maxProfit + dp[i + 1];
    } return result;
}