买卖股票的最好时机 iii_

痛并快乐着、

/*代码是照搬那位叫roundrobin大佬的，加入了一点我自己的理解（拙见）。

题目意思：数组下标为i的元素存储股票i天时的价格，要求进行2次交易，求出最大利益，并且买第2支股票前必须先抛售第一支股票

假如只进行1次交易的话会更简单一些：用sell1表示初始时身上的净利润为0，buy1之后用于存放最便宜股价的价格。一个循环表示时间一天天推移，第一天时buy1记录下第一天买入股票身上净利润，之后每进入新的一天（今天），就用buy1表示前些天最便宜的股价，sell1保存了前些天买入最便宜股票之后再在股价最高时卖出股票的最大利润。新的一天到来，再用buy1继续记录最低股价，再计算出在今天抛售那个最低价股票后的利润，如果这个利润比之前保存的sell1高，那就更新sell1，否则，sell1不变。
如此循环下去，到最后一天结束，sell1就记录了一次交易的最大利润。
进行2次交易的道理是可以类推的。

*/

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int buy1 = INT_MIN, sell1 = 0, buy2 = INT_MIN, sell2 = 0;
        for(auto u:prices) { //每次循环表示进入新的一天
   buy1 = max(buy1,-u);   //记录之前所有天最便宜的股价

            sell1 = max(sell1,buy1 + u); //记录之前所有天只进行1次买卖的最大利益

            buy2 = max(buy2,sell1 - u);   //记录之前天先进行1次交易获得最大利益后，
                   //再买到那次交易后最便宜股价时剩余的净利润

            sell2 = max(sell2,buy2 + u); //记录之前天进行2次完整交易的最大利润
        }

        return sell2;
    }
};

发表于 2017-11-23 22:32:35 回复(3)

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

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)

元气の悟空

class Solution {
public:
    int maxProfit(vector<int> &p) {
        if(p.size()==0||p.size()==1)
            return 0;
        if(p.size()==2)
        	return max(0,p[1]-p[0]);
        int Max=-9999,k;
        for(k=0;k<p.size()-1;k++)
            Max=max(jisuan(p,0,k)+jisuan(p,k+1,p.size()-1),Max);
        Max=max(Max,jisuan(p,0,p.size()-1));
        return Max;
    }
    int jisuan(vector<int> &p,int i,int j)
    {
        int xl[1000],k,Min=9999,Max=-9999;
        for(k=i;k<=j;k++)
        {
            Min=min(Min,p[k]);
            xl[k]=Min;
        }
        for(k=i;k<=j;k++)
            Max=max(Max,p[k]-xl[k]);
        return Max;
    }
};

发表于 2016-08-11 19:22:51 回复(0)

C/C++

J.Fan

class Solution {
public:
      //整体思路是对当前vector中数据进行从前往后和从后往前遍历，从前往后遍历时，
      //记录当前数据之前能够得到的最大差值，从后往前同理得到当前数据之后差值，
     //最后将所有数据前后最大差值相加即为最后所求结果
    int maxProfit(vector<int> &prices) {
        int len = prices.size();
        if(len == 0)
            return 0;
        int *pre = new int[len];
        int *post = new int[len];
        int minN = prices[0];
        pre[0] = 0;
        for(int i=1;i<len;i++)
        {
            pre[i] = max(pre[i-1],prices[i]-minN);
            minN = min(minN,prices[i]);
        }
        int maxN = prices[len-1];
        post[len-1] = 0;
        for(int i=len-2;i>=0;i--)
        {
            post[i] = max(post[i+1],maxN-prices[i]);
            maxN = max(maxN,prices[i]);
        }
        int sum=0;
        for(int i=0;i<len;i++)
        {
            sum = max(sum,pre[i]+post[i]);
        }
        return sum;
    }
};

发表于 2018-07-19 15:27:50 回复(1)

少说多做

别人家小孩的代码，引自leetcode
https://discuss.leetcode.com/topic/5934/is-it-best-solution-with-o-n-o-1
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.
    }
}

发表于 2016-11-06 22:39:19 回复(0)

后劲好大

// 虽然写不出复杂度低且优美简短的代码，氮素胜在满足复杂度以及简单易懂的条件啊！
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1)
        	return 0;
    // 定义两个数组，分别代表从左边，右边开始的最高收益
	int[] left = new int[prices.length];
        int[] right = new int[prices.length];
        
        int leftmin = prices[0];
        int leftmax = 0;
        for(int i = 1; i < prices.length; i++){
        	if(prices[i] > leftmin){
        		int temp = prices[i] - leftmin;
        		if(temp > leftmax){
        			leftmax = temp;
        		}
        		left[i] = leftmax;
        	}        		
        	else{ 
        		leftmin = prices[i];
        		left[i] = left[i - 1];
        	}
        		
        }
        
        int rightmin = prices[prices.length - 1];
        int rightmax = 0;
        for(int i = prices.length - 2; i >= 0; i--){
        	if(prices[i] < rightmin){
        		int temp = rightmin - prices[i];
        		if(temp > rightmax)
        			rightmax = temp;
        		right[i] = rightmax;
        	}
        	else{
        		rightmin = prices[i];
        		right[i] = right[i + 1];
        	}
        }
        
        int max = 0;
        for(int i = 0; i < left.length; i++){
        	int temp = left[i] + right[i];
        	if(temp > max)
        		max = temp;
        }
        return max;
    }
}

发表于 2017-05-12 11:08:35 回复(1)

xiao_lai

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        //You may complete at most two transactions.(you must sell the stock before you buy again)
        //方式一：爆搜 (630ms 8552k)
        /*
        int len=prices.size();
        int maxPro=0;
        for(int i=0;i<len;i++){ //以i作为两次交易的分界线
            int max1=0,max2=0;
            for(int j=0;j<=i;j++){
                for(int k=j+1;k<=i;k++){
                    int val = prices[k]-prices[j];
                    if(val>max1){
                        max1=val;
                    }
                }
            }
            for(int j=i;j<len;j++){
                for(int k=j+1;k<len;k++){
                    int val = prices[k]-prices[j];
                    if(val>max2){
                        max2=val;
                    }
                }
            }
            if(max1+max2>maxPro)maxPro = max1+max2;
        }
        return maxPro;
        */
        
        
        //方式二：波峰波谷检测法，可以减小不必要的搜索空间,相比于第一种效率提升了不少    (180ms 8568k)
        int len = prices.size();
        if(len<=1)return 0;
        vector<int> flag(len,0);
        for(int i=1;i<len-1;i++){
            if(prices[i]>prices[i-1]&&prices[i]>=prices[i+1])flag[i]=1;  //标记为波峰(比较时注意相等情况)
            if(prices[i]<prices[i-1]&&prices[i]<=prices[i+1])flag[i]=-1;  //标记为波谷
        }
        if(prices[0]<=prices[1])flag[0]=-1;
        if(prices[len-1]>prices[len-2])flag[len-1]=1;
        //搜索
        int maxPro=0;
        for(int k=0;k<len;k++){
            int max1=0,max2=0;
            for(int i=0;i<=k;i++){
                if(flag[i]==-1){
                    for(int j=i+1;j<=k;j++){
                        if(flag[j]==1){
                            int val = prices[j]-prices[i];
                            if(val>max1)max1 = val;
                        }
                    }
                }
            }
            for(int i=k;i<len;i++){
                if(flag[i]==-1){
                    for(int j=i+1;j<len;j++){
                        if(flag[j]==1){
                            int val = prices[j]-prices[i];
                            if(val>max2)max2 = val;
                        }
                    }
                }
            }
            int val = max1+max2;
            if(val>maxPro)maxPro = val;
        }
        return maxPro;
    }
};

发表于 2016-07-02 13:45:24 回复(0)

Python

牛客210771号

引例：只能交易一次

首先用 LeetCode121《买卖股票的最佳时机》引出。

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

因为在前后购买的时间点是没有固定的，所以可以考虑「动态规划」的思路来解决。暴力方法就不解释了。

题目中强调只能在 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票，因此，买和卖发生在不同天，不能再同一天完成。这就涉及到在某一天是否持股。

另外，由于需要求得最大的利润，所以，定义动态数组 dp 用来表示当天手中的最大利润。

注意：dp 数组表示某一天结束的时候，手中的利润。（利润指的是手中的现金数，不算已买股票的价值）。

下面按照之前说的四步走的方法进行解题。

一、动态数组定义

dp[i][j],表示持股情况为i，第j天结束，情况下，手中的最大利润。

i代表是否持股，i=0不持股，i=1持股

j代表第j天

所以，dp 是二维数组，并且是 2 行j列的二维数组。

举例：股票每天的价格 prices = [7, 1, 5, 3, 6, 4]

股票-1.png

二、状态转移方程

dp[0][j]：表示该天不持股

很容易想到，如果今天不持股，那么昨天可能持股也可能不持股。分别讨论:

① 今天不持股，并且在昨天也不持股的情况下，手中的利润是不变的：

dp[0][j] = dp[0][j-1]

② 今天不持股，而在昨天持股的情况下，手中的利润一定是增加的（卖掉股票）：

dp[0][j] = dp[1][j-1] + prices[j]

所以，今天的最大价值是：dp[0][j] = max(dp[0][j-1], dp[1][j-1] + prices[j])

dp[1][j]：表示该天持股

① 今天持股，并且在昨天也持股的情况下，手中的利润是不变的：

dp[1][j] = dp[1][j-1]

② 今天持股，而在昨天不持股的情况下，手中的利润一定是减少的，因为进行了买操作：

另外，由于本题规定只发生买卖一次，所以，在发生买操作的时候，直接就是减去当天的股价。

dp[1][j] = -prices[j]

所以，今天的最大价值是：dp[1][j] = max(dp[1][j-1], -prices[j])

三、初始化

如果第 0 天不发生买入操作：dp[0][0] = 0

如果第 0 天发生了买入操作：dp[1][0] = -prices[0]

下面，用一个长图进行一步一步把上述的二维数组填满：

股票-2-1.jpg

股票-2-2.jpg

因为要取最优利润值。所以，卖掉股票后才能有最大利润，除非，一次都没有交易。

故：max_profit = dp[0][-1]

看下核心代码：

def maxProfit(self, prices):
    size = len(prices)
    if size == 0 or size == 1:
        return 0
    # 定义动态数组
    dp = [[0 for _ in range(size)] for _ in range(2)]
    # 初始化动态数组
    dp[0][0] = 0
    dp[1][0] = -prices[0]
    # 动态方程
    for j in range(1, size):
        dp[0][j] = max(dp[0][j - 1], dp[1][j - 1] + prices[j])
        dp[1][j] = max(dp[1][j - 1], -prices[j])
    return dp[0][-1]

是不是看完图中描述和代码后，这个题目的思路就很明显并且很通畅了。

别着急，咱们再看看优化项，除了思路的清晰通畅，看了下面的优化点思路会更加觉得优秀！（呃。。。）

四、优化

在进行每一步计算的过程中可以发现，在每一天的计算中，只与前一天的计算结果有关系，与再之前的数据是没有关系的。

比如，在计算第 3 天的利润时，只与第 2 天的两个状态下的值有关系。

所以，只需要保留两个变量就可以将空间方面进行优化。可以动手按照上述思路画一下，很清晰的思路就出来了。

空间方面的优化代码：

def maxProfit_opt(self, prices):
    size = len(prices)
    if size == 0 or size == 1:
        return 0
    dp1 = 0
    dp2 = -prices[0]
    for j in range(1, size):
        tmp1 = max(dp1, dp2+prices[j])
        tmp2 = max(dp2, -prices[j])
        dp1, dp2 = tmp1, tmp2
    return dp1

无限制买卖

上面 LeetCode121 题目限制了在给定的范围内，只能进行一次买卖。

下面的 LeetCode122 无限制进行买卖，进行求解最大利润。

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

近乎同样的解决逻辑，只是在进行买入股票的时候需要考虑之前的利润状态，上一个题目买入股票不需要考虑之前的利润状态，因为只进行一次买卖。

还是详细的来说说，每个步骤具体怎么状态转移。

一、动态数组定义

dp[i][j],表示持股情况为i，第j天结束，情况下，手中的最大利润。

i代表是否持股，i=0不持股，i=1持股

j代表第j天

所以，dp 是依然是二维数组，并且是 2 行j列的二维数组。

举例：股票每天的价格 prices = [7, 1, 5, 3, 6, 4]

股票-1.png

二、状态转移方程

dp[0][j]：表示该天不持股

很容易想到，如果今天不持股，那么昨天可能持股也可能不持股。分别讨论:

① 今天不持股，并且在昨天也不持股的情况下，手中的利润是不变的：

dp[0][j] = dp[0][j-1]

② 今天不持股，而在昨天持股的情况下，手中的利润一定是增加的：

dp[0][j] = dp[1][j-1] + prices[j]

今天的最大价值是：dp[0][j] = max(dp[0][j-1], dp[1][j-1] + prices[j])

dp[1][j]：表示该天持股

① 今天持股，并且在昨天也持股的情况下，手中的利润是不变的：

dp[1][j] = dp[1][j-1]

② 今天持股，而在昨天不持股的情况下，手中的利润一定是减少的，因为进行了买操作：

因为无限次买卖。所以，在发生买操作的时候，需要将之前的利润状态减去当天的股价。

dp[1][j] = dp[0][j-1] - prices[j]

所以，今天的最大价值是：dp[1][j] = max(dp[1][j-1], dp[0][j-1] - prices[j])

三、初始化

如果第 0 天不发生买入操作：dp[0][0] = 0

如果第 0 天发生买入操作：dp[1][0] = -prices[0]

下面，依然用一个长图进行一步一步把上述的二维数组填满：

股票-3-1.png

股票-3-2.png

最后拿到dp[0]的最后一个元素就是最大利润值，因为不持股手中的利润就是多的情况。

即：max_profit = dp[0][-1]

核心代码：

def maxProfit(self, prices):
    size = len(prices)
    if size == 0 or size == 1:
        return 0
    # 定义动态数组
    dp = [[0 for _ in range(size)] for _ in range(2)]
    # 初始化动态数组
    dp[0][0] = 0
    dp[1][0] = -prices[0]
    # 动态方程
    for j in range(1, size):
        dp[0][j] = max(dp[0][j - 1], dp[1][j - 1] + prices[j])
        dp[1][j] = max(dp[1][j - 1], dp[0][j - 1] - prices[j])
    print(dp)
    return dp[0][-1]

四、优化

同样的优化方案，还是从空间的角度进行优化。

同样很显然的，每一天利润值计算无论是买股票还是卖股票，都是只与前一天有关系。

因此，只需要设置两个值（dp1、dp2）存放持有和不持有股票的最大利润值，就可以简化空间计算。

核心代码：

def maxProfit_opt(self, prices):
    size = len(prices)
    if size == 0 or size == 1:
        return 0
    # 初始化动态数组
    dp1 = 0
    dp2 = -prices[0]
    for j in range(1, size):
        tmp1 = max(dp1, dp2 + prices[j])
        tmp2 = max(dp2, dp1 - prices[j])
        dp1, dp2 = tmp1, tmp2
    return dp1

以上，在 LeetCode 中都属于 easy 模式的题目。

如果说，在一段时间内，只允许交易固定次数的时候，该怎么做？

比如，在 6 天时间内，允许交易 2 次，求最大利润？或者交易 k 次，求最大利润？

交易 2 次，最大利润？

下面的 LeetCode123 规定只进行 2 次买卖，进行求解最大利润。

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

还有一点注意，之前的题目强调，同一天不能既买又卖，但是当前的问题没有强调这一点，是可以在同一天进行买卖的。

思路和之前的题目还是有一点区别的，建议一定细致读每一个字。

下面详细的来说说，每个步骤具体怎么状态转移。

一、动态数组定义

dp[i][j]，代表进行i次交易，在第j天的时候的最大利润。

i代表交易次数

j代表天数

举例：股票每天的价格 prices = [1, 3, 0, 2, 1, 5]

根据案例，定义 dp 数组为 3 行 6 列。

股票-4.png

二、状态转移方程

和之前的有点不一样

动态方程：dp[i][j]=max{dp[i][j-1], max{prices[i]-prices[n]+dp[i-1][n]}}, n=0,1,…,j-1

看起来很复杂，公式复杂，其实思路还是比较简单。

不要着急，也不要被吓退，后面会每一步将上述动态数组填满，填满之后发现真的比较简单。

三、初始化

dp[0]=0：如果一直进行 0 次交易。那么，无论到第几天，利润都为 0

dp[1][0]：第 0 天，进行 1 次交易，无论是买、卖还是买+卖都进行，最大利润必为 0

dp[2][0]：第 0 天，进行 2 次交易，无论是买、卖还是买+卖都进行，最大利润还为 0

初始化之后，就可以将上述二维数组填满，即可清晰看到每一步的计算过程。

【建议查看高清图片或者直接到 github 进行读取】

股票-6.png

注意，以上红框中也是要取最大值，对应动态方程中的第二个max。下面所有图示均符合此规律。

股票-5.png

上述步骤中，只填写了第i=1这一行。

最大利润值，要么取前一天的数据，要么就是公式中的计算逻辑。取其最大值。

下面再把第i=2这一行填完，大家的思路会更加清晰起来。

股票-7.png

这一顿操作，我简直差点要放弃了。

就按照上述思路，代码下来，发现执行超时，又一次差点放弃解答。

也不可谓难度为困难，而困难点就在这里。

至此，必须要进行优化，将时间复杂度降低下来。一般来说，动态规划的题目是将空间复杂度降低，时间复杂度降低的题目相对比较少一点。

四、优化

从上面图中，很容易发现一点重复计算的部分。

下面就拿出来最后 2 个步骤的其中一些公式对照：

prices[4]-prices[0]+dp[0][0]
prices[4]-prices[1]+dp[0][1]
prices[4]-prices[2]+dp[0][1]
prices[4]-prices[3]+dp[0][1]

和

prices[5]-prices[0]+dp[0][0]
prices[5]-prices[1]+dp[0][1]
prices[5]-prices[2]+dp[0][1]
prices[5]-prices[3]+dp[0][1]
prices[5]-prices[4]+dp[0][1]

可以明显看出来，上述被标注的部分又是重复的计算。

最左侧一列都是当前的股票价格，也是不变的。

那么，这个时候就可以使用一个变量max_profit来进行记录右侧被标记部分的最大值。

将之前的动态方程：

dp[i][j]=max{dp[i][j-1], max{prices[i]-prices[n]+dp[i-1][n]}}, n=0,1,…,j-1

改为：

dp[i][j]=max{dp[i][j-1], prices[j]+max_profit}

其中，max_profilt=max{dp[i-1][j]-prices[j], max_profit}

这里这里这里很重要，一定画图理解。

也许就是该题目难度被设置为“困难”的地方！

看代码，很简单的实现：

def maxProfit(self, prices):
    """
    使用动态规划解决: 最多完成 2 次交易
    """
    size = len(prices)
    if size == 0:
        return 0
    dp = [[0 for _ in range(size)] for _ in range(3)]
    print(dp)
    for i in range(1, 3):
        # 每一次交易的最大利润
        max_profit = -prices[0]
        for j in range(1, size):
            dp[i][j] = max(dp[i][j-1], max_profit + prices[j])
            max_profit = max(max_profit, dp[i-1][j] - prices[j])
    print(dp)
    return dp[-1][-1]

这样就完美解决了！

交易多次，最大利润？

LeetCode123 规定最多交易 2 次，下面再上升一个难度。

在 LeetCode188. 买卖股票的最佳时机 IV，最多可以完成 k 笔交易，求最大的利润。

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

如果 LeetCode123 题目理解清楚的话，这个题目很快就可以解决了。

上一题规定最多交易 2 次，改题目最多交易 k 次。即：把 2 次的逻辑换为 k 次逻辑，就可以解决了。

直接看代码吧，和上一个题很类似：

def maxProfit(self, k, prices):
    size = len(prices)
    if size == 0:
        return 0
    dp = [[0 for _ in range(size)] for _ in range(k+1)]
    print(dp)
    for i in range(1, k+1):
        # 每一次交易的最大利润
        max_profit = -prices[0]
        for j in range(1, size):
            dp[i][j] = max(dp[i][j-1], max_profit + prices[j])
            max_profit = max(max_profit, dp[i-1][j] - prices[j])
    print(dp)
    return dp[-1][-1]

看出来不一样的地方了吧，就是在之前逻辑设置为 2 的地方，在本地改为 k 次即可！

注意：之前是 range(1, 3)代表 1 和 2， range(1,k+1) 代表 1,2,3,...,k

以上！

《买卖股票的最佳时机》系列题目详细的进行了解释，后面还有其他的股票相关题目，但基本是基于今天文章的思路进行解决的。

刷题计划已经进行了有一段时间，需要一起来搞的，加我微信，我拉你进群哈！

vx: xiaozhu_tec（备注“牛客”）

传送门：代码 & 文档

代码和本文的文档都在 https://github.com/xiaozhutec/share_leetcode 需要的小伙伴可以自行下载代码运行跑起来！方便的话给个 star。谢过大家！

发表于 2021-09-03 23:38:48 回复(1)

C/C++

Dancer_Wu

想不出大佬们那种高效的思路，自己瞎搞了一下(大佬的思路真的要好好学，很棒)

1，整个问题整体就是低点买，高点卖；

2，通过一次遍历，找出极值点（极小--极大），存储；

3. 从存储的数据对中，分割数据，求两段数据的最大总和，取最大值；

class Solution {
public:
 int maxP(vector<int> prices,int a,int b)   //一段中的最大效益
{
	int mins = prices[a], maxs = 0;
	for (int i = a; i <= b; i++)
	{
		mins = min(mins, prices[i]);
		maxs = max(maxs, prices[i] - mins);
	}
	return maxs;
}
 int maxProfit(vector<int> &prices) {
       
	if (prices.size() <= 1)  return 0;    //数据小于两个
	int mins = prices[0], maxs = prices[0];
	int flag = 0;
	vector<int> cons;    //存储峰值对
	for (int i = 0; i < prices.size(); i++)   //遍历求峰值对
	{
		if (mins >= prices[i] && flag == 0) mins = prices[i];
		else
		{
			if (prices[i] > prices[i - 1])
			{
				maxs = prices[i];
				flag = 1;
			}
			else
			{
				cons.push_back(mins);
				cons.push_back(maxs);
				mins = prices[i];
				maxs = prices[i];
				flag = 0;
			}
		}
	}
	if (mins != prices[prices.size() - 1])
	{
		cons.push_back(mins);
		cons.push_back(maxs);
	}
	if (cons.size() == 2)  return cons[1] - cons[0];
	int maxz=0;
	for (int i = 1; i < cons.size(); i += 2)   //分段，求最大效益和
	{
		maxz = max(maxz, maxP(cons, 0, i) + maxP(cons,i + 1, cons.size() - 1));
	}
	return maxz;
    }
};

发表于 2020-04-18 21:35:13 回复(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)

yf.dl

buy表示买入时的收益

sell表示卖出时的收益

class Solution {
public:
  int maxProfit(vector<int> &prices) {
      int n = prices.size();
      if (n < 2) return 0;
      int buy1 = INT_MIN, sell1 = 0;
      int buy2 = INT_MIN, sell2 = 0;
      for (int i = 0; i < n; i++) {
          buy1  = max(buy1,  0     - prices[i]); // 买入减收益
          sell1 = max(sell1, buy1  + prices[i]); // 卖出增收益
          buy2  = max(buy2,  sell1 - prices[i]); // 买入减收益
          sell2 = max(sell2, buy2  + prices[i]); // 卖出增收益
      }
      return sell2;
  }
};

发表于 2018-09-03 00:16:51 回复(0)

C/C++

nbgao

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int b1 = INT_MIN, s1 = 0, b2 = INT_MIN, s2 = 0;
        for(int p:prices)
        {
        	b1 = max(b1, -p);
        	s1 = max(s1, b1+p);
        	b2 = max(b2, s1-p);
        	s2 = max(s2, b2+p);
		}
		return s2;
    }
};

发表于 2017-09-03 01:27:00 回复(0)

sky_

//左右两边扫一遍，对于当前准备卖股票的点i，最大收益需要算出，前i-1个位置最低点，从i+1
//往后开始的最大收益，所以分别维护下最大最小值就好了。 class Solution {
public:
    int maxProfit(vector<int> &p){
        if(p.size()==0) return 0;
        vector<int> l(p.size()+5,0),r(p.size()+5,0);
        int minn=0x7f7f7f7f,maxn=-1,ans=0;
        for(int i=0;i<p.size();i++)
           l[i]=max(p[i]-minn,i>=1?l[i-1]:0),minn=min(minn,p[i]);
        for(int i=p.size()-1;i>=0;i--)
           r[i]=max(maxn-p[i],(i<p.size()-1)?r[i+1]:0),maxn=max(maxn,p[i]);
        for(int i=0;i<p.size();i++) ans=max(ans,l[i]+r[i+1]);
        return ans;
    }
};

发表于 2017-07-26 16:11:13 回复(0)

JacobGo！

public int maxProfit(int[] prices) {
		if (prices == null || prices.length < 2)
			return 0;
		// 四个变量分别表示经过当前操作以后的profit
		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, curPrice + firstBuy);
			secondBuy = Math.max(secondBuy, firstSell - curPrice);
			secondSell = Math.max(secondSell, secondBuy + curPrice);
		}
		return secondSell;
	}

发表于 2017-07-15 10:47:25 回复(1)

曾~

/*第一步先计算出子序列[0,...,i]中的最大利润，用一个数组保存下来，那么时间是O(n)。
*第二步是计算子序列[i,...,n-1]上的最大利润，，这一步也是O(n)。
*结合上俩步的结果计算最终的最大利润，所以最终算法的复杂度就是O(n)的。
**/
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0)
            return 0;
        int n=prices.length;
        int[] pro=new int[n];
        int[] rpro=new int[n];
        int ans=0;
        int low=prices[0];
        int high=prices[n-1];
        int res=0;
        for(int i=1;i<n;++i){
            if(prices[i]<low){
                low=prices[i];
            }
             else if(ans<prices[i]-low){
                 ans=prices[i]-low;
             }
            pro[i]=ans;
        }
        ans=0;
        for(int j=n-2;j>=0;--j){            
            if(prices[j]>high)
                high=prices[j];
            else if(ans<high-prices[j]){
                ans=high-prices[j];
            }
            rpro[j]=ans;
        }
        for(int i=0;i<n;++i){
            ans=pro[i]+rpro[i];
            if(ans>res)
                res=ans;
        }
        return res;
    }
}

发表于 2017-04-25 11:46:34 回复(1)

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)

已注销

int getmax(vector<int> a, int left, int right)
   {
       if (left >= right)return 0;
       int profit = 0;
       int cur_min = a[left];
       for (int i = left; i <=right; i++)
       {
           if (a[i] - cur_min > profit)profit = a[i] - cur_min;
           if (a[i] < cur_min)cur_min = a[i];
       }
       return profit;
   }
   int calculateMax(vector<int> prices) {
       int max = 0;
       for (int i = 0; i < prices.size(); i++)
       {
           if (getmax(prices, 0, i) + getmax(prices, i, prices.size() - 1)>max)
           {
               max = getmax(prices, 0, i) + getmax(prices,i, prices.size() - 1);
           }
       }
       return max;
   }

编辑于 2016-03-19 18:35:03 回复(0)

C/C++

xyxlil

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy1 = INT_MIN, sell1 = 0, buy2 = INT_MIN, sell2 = 0;
        for(int i = 0; i < prices.size(); i++) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};

发表于 2017-01-22 14:26:47 回复(15)

牛客566865863号

这个有这么难理解么.....分治法不就行了么....

将数组分为两段，每一段就是一次交易。那么前段的最大收益+后段的最大收益=整体最大收益，然后每次比较下在哪里分段是最高的收益就行了

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     *将数组分为两段，前段的最大收益+后段的最大收益=整体最大收益
     
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int result = 0;
        for(int i = 0; i < prices.size(); i++){
            vector<int> front;
            front.assign(prices.begin(), prices.begin() + i);
            vector<int> back;
            back.assign(prices.begin() + i, prices.end());
            //前段最大收益+后段最大收益，然后每次比较下哪种分段是最高的
            result = max(result, maxPrice(front) + maxPrice(back));
        }
        
        return result;
    }
    
    //求每一段的最大收益
     int maxPrice(vector<int>& prices) {
        // write code here
         if(prices.size() <= 1){
             return 0;
         }
        int result = 0;
        int temp = prices[0];
        for(int i = 0; i < prices.size(); i++){
            temp = min(temp,prices[i]);
            result = max(result, prices[i] - temp);
        }
        return result;
    }
};

发表于 2021-02-03 17:47:00 回复(0)

买卖股票的最好时机 iii

输入

输出

输入

输出

引例：只能交易一次

一、动态数组定义

二、状态转移方程

三、初始化

四、优化

无限制买卖

一、动态数组定义

二、状态转移方程

三、初始化

四、优化

交易 2 次，最大利润？

一、动态数组定义

二、状态转移方程

三、初始化

四、优化

交易多次，最大利润？

传送门：代码 & 文档

问题信息

热门推荐

通过挑战的用户

相关试题

买卖股票的最好时机 iii

输入

输出

输入

输出

引例：只能交易一次

一、动态数组定义

二、状态转移方程

三、初始化

四、优化

无限制买卖

一、动态数组定义

二、状态转移方程

三、初始化

四、优化

交易 2 次，最大利润？

一、动态数组定义

二、状态转移方程

三、初始化

四、优化

交易多次，最大利润？

传送门： 代码 & 文档

问题信息

热门推荐

通过挑战的用户

相关试题

传送门：代码 & 文档