买卖股票的最佳时机III

这是上一道题的升级版。上一道题是在一段时间内可以无限次数的买入和卖出，这题是限定只能两次买入和卖出。这样难度就增加了不少。（具有三年以上的股票买卖者会选择这种，利用最小次数的买入和卖出来获取最大的利润）

123买卖股票的最佳时机III

题目：

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例1：

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例2：

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例3：

输入: [7,6,4,3,1] 
输出: 0 
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

题解如下：

• 1、因为最多只能进行两次交易，所以可以将时间划为二部分，分别找出这两段时间内进行一次所获得（这样就不能出现交叉交易的情况），将两者相加就是在这种情况下最多进行两次交易所能获取的最大利润。为了降低复杂的划分，我们可以先从前往后遍历，并缓存最多一次交易所能获取的最大利润；然后在从后往前计算最多进行一次交易所能获取的最大交易，与对应缓存相加就是在一次划分下的最大的利润。

image.png

• 2、将M1、M2中对应的第i处的值相加起来，最终获得最大利润。

代码如下：

package com.zhoujian.solutions.didi;
import java.util.Scanner;
/**
 * @author zhoujian123@hotmail.com 2018/9/9 14:41
 */
public class Stock3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] split = s.split(",");
        int n = split.length;
        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = Integer.parseInt(split[i]);
        }
        int max_profit = maxProfit(prices);
        System.out.println(max_profit);
    }

    private static int maxProfit(int[] prices) {
        int N = prices.length;
        if(N == 0) return 0;
        //存放利润
        int[] M1 = new int[N];
        int[] M2 = new int[N];

        //从左到右遍历
        int minPrice = prices[0];
        for(int i = 1; i < N; i++){
            minPrice = Math.min(minPrice, prices[i]);
            M1[i] = Math.max(M1[i-1], prices[i]-minPrice);
        }

        //从右到左遍历
        int maxPrice = prices[N-1];
        for(int i = N-2; i >= 0; i--){
            maxPrice = Math.max(maxPrice, prices[i]);
            M2[i] = Math.max(M2[i+1], maxPrice-prices[i]);
        }
        //获取最大利润
        int best = 0;
        for(int i = 0; i < N; i++){
            best = Math.max(best, M1[i]+M2[i]);
        }
        return best;

    }
}

结果如下：

image.png

• 时间复杂度为O(n)，空间复杂度为O(n)。