买卖股票的最好时机 ii

class Solution {
    /**
     *  继续上一题思路，继续用转移方程
     *  假设第i天持有股票的收益为f(i,1),未持有的收益为f(i,0)
     *  f(i,1) = max(f(i-1, 1), f(i-1, 0)-prices[i])
     *  f(i,0) = max(f(i-1, 0), f(i-1, 1)+prices[i])
     *  f(0,0) = 0, f(0,1)=-prices[0];
     *  还有一个思路是遍历判断前后两天的收益，是正的就累计
     *  因为不限制交易次数，可以在跌了前卖出，涨之前买入
     *  吃掉所有利差
     */
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int i0=0, i1=-prices[0];
        for(int i=0; i<prices.length; i++){
            int j0 = Math.max(i0, i1+prices[i]);
            int j1 = Math.max(i1, i0-prices[i]);
            i0=j0;
            i1=j1;
        }
        return i0;
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        //不限次数的交易，最大利润就是每次买入都是涨价的，所有涨的都有份，跌的时候早就卖了
        int max=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]>prices[i-1])
                max += prices[i]-prices[i-1];
        }
        return max;
    }
}

public class Solution {
	 public int maxProfit(int[] prices) {
		 if(prices.length<=1) return 0;
		 int profit = 0;
		 for(int i=1; i<prices.length; i++) profit += Math.max(prices[i]-prices[i-1], 0);
		 return profit;
	 }
}

class Solution {
public:
    int maxProfit(vector<int> &prices) {
    	if (prices.size() <= 1) {
    		return 0;
    	}
    	int profit = 0;
        int i = 0;
        int j = 1;
        while (j < prices.size()) {
        	if (prices[j] < prices[j-1]) {
        		profit += prices[j-1] - prices[i];
        		i = j;
        	}
        	++j;
        	if (j == prices.size()) {
        		profit += prices[j-1] - prices[i];
        	}
        }
        return profit;
    }
};

public class Solution {
    public int maxProfit(int[] prices) {//这次的真简单，比第一道简单多了，相邻只要是上升的就要了
        int sum =0;
        for(int i=0;i<prices.length-1;i++){
            if(prices[i]<prices[i+1]){
                sum+=prices[i+1]-prices[i];
            }
        }
        return sum;
    }
}

public class Solution {//所有递增子区间
    public int maxProfit(int[] prices) {
        int res=0;
        int index=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]<prices[i-1]){
                res+=(prices[i-1]-prices[index]);
                index=i;
            }
            if(i==prices.length-1){
                res+=(prices[i]-prices[index]);
            }
        }
        return res;
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 1; i < prices.length; i++) max += Math.max(0, prices[i] - prices[i-1]);
        return max;
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length<2)
            return 0;
        int res = 0;
        for(int i =1;i<prices.length;i++){
            if(prices[i]>prices[i-1])
                res += prices[i]-prices[i-1];
        }
        return res;
    }
}

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        //本题由于允许多次交易（每次必须先卖出再买进），所以不好用爆搜
        //分析可知，要想利益最大化，就应该每次在波谷买进，波峰卖出，这样利益最大，操作次数最少
        //应该是使用动态规划来做可能比较简洁，个人觉得。
        
        int len = prices.size();
        vector<int> change(len,0);
        int maxPro=0;
        for(int i=1;i<len;i++){
            change[i]=prices[i]-prices[i-1];  //记录所有长和跌的情况
            if(change[i]>0)maxPro += change[i];  //累加所有长幅，即为最大收益
        }
        return maxPro;
    }
};

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len==0)
            return 0;
        int buyin = prices[0];
        int[] dp = new int[len];
        dp[0]=0;
        for(int i=1;i<len;i++){
            dp[i] = Math.max(dp[i-1],dp[i-1] + prices[i]-buyin);
            buyin = prices[i];               
        }
        return dp[len-1];
    }
}

int maxProfit(vector<int> &prices) {
        int max_profit=0;
        int length=prices.size();
        if(length==1)
            return 0;
        for(int i=1;i<length;i++){
            int sum=prices[i]-prices[i-1];
            if(sum>0)
                max_profit += sum;
        }
        return max_profit;
    }

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int sum=0;
        // write code here
        //建立两个定位下标
        //接收到一个数组 第一个元素比第二个元素大{4.1.2.3
        if(prices==null || prices.length==0)
        {
            return 0;
        }
        for(int i=0;i<prices.length-1;i++)
        {
            int j=i+1;
            if(prices[i]<prices[j])
            {
                sum+=prices[j]-prices[i];
                
                
            }

        }
        
 return sum;
        }
        
    }

引例：只能交易一次

首先用 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]

二、状态转移方程

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]

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

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

故：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]

二、状态转移方程

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]

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

最后拿到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 列。

二、状态转移方程

和之前的有点不一样

动态方程：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 进行读取】

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

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

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

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

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

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

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

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

四、优化

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

下面就拿出来最后 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。谢过大家！

class Solution:
    def maxProfit2(self , prices ):
        if len(prices) == 0:
            return 0
        buyin = prices[0]
        dp = [0]
        for i in range(len(prices)-1):
            temp = max(dp[i],dp[i]+prices[i+1]-buyin)
            dp.append(temp)
            buyin = prices[i+1]
        return dp[-1]

//在自己电脑上运行结果正确，但是在平台上运行保错

	请检查是否存在数组越界等非法访问情况



	case通过率为0.00% Exception in thread "main" java.lang.StackOverflowError at Solution.getProfit(Solution.java:33) 

import java.util.*;
public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    static int maxP=0;
    static public int maxProfit (int[] prices) {
        // write code here
        getProfit(prices,0,false,0);//初始化buy=false未购买。cost=赚的钱
        return maxP;
    }
     static public int getProfit(int[] prices, int day,boolean buy,int cost){
        if(day==prices.length-1){//假设还有一天买卖的机会
            if(buy){
                cost=cost+prices[day];//一定会卖出去
            }
            if(cost>maxP)
                maxP=cost;
            return cost;
        }

        int cost1,cost2;
        //遍历所有的情况
        if(buy){//如果已经买了，则可能卖，也可能不卖。
            cost1=getProfit(prices,day+1,false,cost+prices[day]);//卖出去
            cost2=getProfit(prices,day+1,true,cost);//没有卖
        }
        else{//如果还没买，可能买也可能不买。
            cost1=getProfit(prices,day+1,false,cost);//没有买
            cost2=getProfit(prices,day+1,true,cost-prices[day]);//买了
        }
        return Math.max(cost1,cost2);

    }

}

首先思考一个问题，假如让我们手动进行操作会怎么操作？

比如[1, 4, 2, 1, 8, 7, 9, 2]，直观的感受是遇到递增序列即执行买入卖出，如：

1. 1, 4递增，1买4卖
2. 1, 8递增，1买8卖
3. 7，9递增，7买9卖

代码如下：

//
// Created by jt on 2020/9/24.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param prices int整型vector
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        if (prices.size() < 1) return 0;
        int res = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] > prices[i-1]) res += prices[i] - prices[i-1];
        }
        return res;
    }
};