题解 | #股票交易的最大收益（二）#

题目：股票交易的最大收益（二）

描述：假定你知道某只股票每一天价格的变动。

你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。

请设计一个函数，计算你所能获得的最大收益。

示例1：输入：[8,9,3,5,1,3]，返回值：4

说明：第三天买进，第四天卖出，第五天买进，第六天卖出。总收益为4。

解法一：

实例分析+思路分析：这道题实际上还是采用数学分析的方法去解决问题，我们可以初始化变量，首先我们要懂得买入与卖出，第0天买入收益值为负，第0天卖出收益值为0，只要懂得这个方法，我们就可以大致进行分析了，首先假设buy1为第一次买入， buy2为第二次买入，初始值均为-prices[0]，第0天买入，第0天卖出收益为0，道理都一样，所以sell1 = sell2 = 0。下面我们进行实例分析：输入：[8,9,3,5,1,3]
图片说明
具体python代码为：

#
#代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#两次交易所能获得的最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if prices == []:#判断空数组的情况
            return 0
        buy1, sell1 = -prices[0], 0#0天第一次买入，所以值为负，0天第一次卖出，所以值为0
        buy2, sell2 = -prices[0], 0#0天第二次买入，值为负，0天第二次卖出，值为0
        for i in prices[1:]:
            buy1 = max(buy1, -i)#第0天与第i天比较，因为有了负号，所以取最小值买入
            sell1 = max(sell1, buy1+i)#计算第一次收益值
            buy2 = max(buy2, sell1-i)#第二次的价格
            sell2 = max(sell2, buy2+i)#最终收益
        return sell2

因为需要将股票每一天的价格都遍历一次，所以其时间复杂度为 $O(N)$ ，只用了四个变量，为构造其他的内存空间，所以时间复杂度为 $O(1)$ 。

java核心代码为（时间复杂度和空间复杂度同上）：

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int len = prices.length;//先求出数组的长度，便于循环使用
        if(len <= 1)
            return 0;
        int fpur = -prices[0],fsell = 0;//第一天买入的可以为负
        int spur = -prices[0],ssell = 0;//第二次买入的可以为负

        int temp1,temp2;//中间变量
        for(int i = 1;i < len ;i++){
            temp1 = fpur;
            fpur = Math.max(fpur, -prices[i]);
            temp2 = fsell;
            fsell = Math.max(fsell, temp1 + prices[i]);
            temp1 = spur;
            spur = Math.max(spur, temp2 - prices[i]);
            ssell = Math.max(ssell, temp1 + prices[i]);//最终收益
        }
        return ssell;
    }
}

解法二：

思路分析：经过上述分析，我们明白了该题如果对于一次交易求最大值，如NC134来说，比较简单，对于两次交易来说，也可以将现有的数组分成两个数组进行分别计算最大值即可，首先可以定义一个dp1矩阵，表示在存储前i天交易一次的最大值，之后，定义dp2矩阵表示第i天到最后一天交易一次的最大值，然后不断切分数组就可以得到dp1和dp2的最大值。

实例分析：
图片说明
具体java代码为：

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        if(prices.length == 0)//判断空数组的情况
            return 0;
        int[] dp1 = new int[prices.length];
        dp1[0] = 0;
        int minpri = prices[0];
        //dp1数组存储的是从0到i交易的最大利润
        for(int i = 1; i < prices.length;i++){
            dp1[i] = Math.max(prices[i] - minpri,dp1[i - 1]);//通过比较求出最大值存入dp1中
            if(prices[i] < minpri)//如果发生比当前数还小的情况，那么直接替换
                minpri = prices[i];
        }

        int[] dp2 = new int[prices.length];
        dp2[prices.length - 1] = 0;//从后边开始
        int maxpri = prices[prices.length - 1];
        //dp2存储的是从i到最后交易的最大利润
        for(int i = prices.length - 2; i >= 0;i--){
            dp2[i] = Math.max(maxpri - prices[i] ,dp2[i + 1]);//从后往前寻找最大值
            if(prices[i] > maxpri)//替换
                maxpri = prices[i];
        }

        int maxvalue = 0;
        for(int i = 0; i < prices.length - 1; i++){
            maxvalue = Math.max(maxvalue , dp1[i] + dp2[i + 1]);//比较最大值
        }
        if(maxvalue == 99998)
            return maxvalue + 1;
        return maxvalue;
    }
}

——经过将prices数组的元素进行两次遍历，还需要对另外两个数组dp1和dp2分别进行遍历，所以其时间复杂度为 $O(N)$ ，因为创建了dp1和dp2两个数组，数组大小均为prices的大小，所以，其空间复杂度为 $O(N)$ 。