题目描述

在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于2)，规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列，请写一个程序计算一天可以获得的最大收益。请采用实时间复杂度低的方法实现。

给定价格序列prices及它的长度n，请返回最大收益。保证长度小于等于500。

测试样例：

[10,22,5,75,65,80],6

返回：87

代码

    public static int calculateMax(int[] prices) {
        int buyone = -100;// 买了第一波之后剩下的钱
        int sellone = 0;// 卖了第一波之后剩下的钱
        int buytwo = -100;// 买了第二波之后剩下的钱
        int selltwo = 0;// 卖了第二波之后剩下的钱
        for (int cur : prices) {
            // 找一把最低价买入，buyone存的是买入后的钱，是负数
            buyone = Math.max(buyone, -cur);
            System.out.println(buyone + " " + -cur);
            // 看是上一把卖掉好，还是这一把卖掉好
            sellone = Math.max(sellone, buyone + cur);
            System.out.println(sellone + " " + (buyone + cur));
            // 找第二把较低价买入，buytwo存的是现在的钱量
            buytwo = Math.max(buytwo, sellone - cur);
            System.out.println(buytwo + " " + (sellone - cur));
            // 看是上一把卖了好还是这一把，cur+buytwo是说现在的钱加上现在持有的股票的价值的和
            selltwo = Math.max(selltwo, cur + buytwo);
            System.out.println(selltwo + " " + (cur + buytwo));
            System.out.println(buyone + " " + sellone + "\t" + buytwo + " " + selltwo + "\n");

            // 每个变量都是依靠上一个变量来的，所以可以看作是有先后顺序的
        }
        return selltwo;
    }