股票买卖Ⅲ

问题陈述

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

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

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

1
2
3
4
5
6
示例 1:

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

思路实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//只能进行两次交易，求最大利润。
private static int buySockets3(int[] prices){
    if(prices==null || prices.length==0) return 0;
    int len= prices.length;
    int min = prices[0];            // 初始化的前半部分最小买入价格
    int max = prices[len - 1];      // 初始化的后半部分最大卖出价格
    int maxPro1 = 0;                // 前半部分的每天最大利润
    int maxPro2 = 0;                // 后半部分的每天最大利润
    int[] profit1 = new int[len];   // 前半部分的利润表
    int[] profit2 = new int[len];   // 后半部分的利润表
    for(int i=0;i<prices.length;i++){
        //前半部分的利润表
        if(prices[i]<=min){
            min=prices[i];
        }else{
            maxPro1=Math.max(maxPro1,prices[i]-min);
        }
        profit1[i]=maxPro1;
        //后半部分的利润表
        if(prices[prices.length-i-1]>=max){
            max=prices[prices.length-i-1];
        }else{
            maxPro2=Math.max(maxPro2,max-prices[prices.length-i-1]);
        }
        profit2[prices.length-i-1]=maxPro2;
    }
    int res=Integer.MIN_VALUE;
    for(int i=0;i<prices.length;i++){
        res=Math.max(res,profit1[i]+profit2[i]);
    }
    return res;
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int maxProfit(int[] prices) {
      
      int minPrice1 = Integer.MAX_VALUE;         
      int maxProfit1 = 0;                        
      int maxProfitAfterBuy = Integer.MIN_VALUE; 
      int maxProfit2 = 0;                        
      for(int price : prices) {
          // 1.第一次最小购买价格
          minPrice1  = Math.min(minPrice1,  price);

          // 2.第一次卖出的最大利润
          maxProfit1 = Math.max(maxProfit1, price - minPrice1);

          // 3.第二次购买后的剩余净利润
          maxProfitAfterBuy  = Math.max(maxProfitAfterBuy,  maxProfit1 - price );

          // 4.第二次卖出后，总共获得的最大利润（第3步的净利润 + 第4步卖出的股票钱）
          maxProfit2 = Math.max(maxProfit2, price + maxProfitAfterBuy);
      }
      return maxProfit2;
  }