[数据结构与算法]0动态规划中等 NC135 股票交易的最大收益（二）

NC135 股票交易的最大收益（二）

描述

假定你知道某只股票每一天价格的变动。
你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。
请设计一个函数，计算你所能获得的最大收益。

分析

最后一次交易时，只有五种状态：1.没有交易；2.买了一只股票；3.卖了第一支股票；4.买了第二只股票；5.卖了第二只股票。
因为买股票是花钱，所以最大收益一定是：1，3，5中的一个。
1.没有交易。一直是0，直接起点的时候与0比较，不做分析。
2.买了一只股票。可能是今天买的，也可能是前几天买的。
3.
4.
5.

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        int n = prices.length;
        if(n == 0){
            return 0;
        }
        int buy1 = -prices[0], buy2 = -prices[0];//买股票花的钱。
        int sell1 = 0, sell2 = 0;//还没有买所以是0，或者理解为买了又卖了没赚到钱。
        for(int i = 1; i < n; i++){
            buy1 = Math.max(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 Math.max(sell1, sell2);
    }
}