最多n次购买时股票最大收益问题

一般我们常见的股票最大收益问题是：

已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。 假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。 设计算法，计算你能获得的最大收益。 输入数值范围：2<=n<=100,0<=prices[i]<=100

这道算法比较容易理解的思想是：在对股票进行迭代遍历的过程中，用四个变量（第一、二次买入和卖出时的最大收益）记录当前的最大收益值，即记录当前的最优解。所以这道题可以用动态规划来解决。

针对这个问题的求解Java代码如下（带详细注释）：

public class Solution {
       /**
     * 计算你能获得的最大收益
     *
     * @param prices Prices[i]即第i天的股价
     * @return 整型
     */
    public int calculateMax(int[] prices) {
        // 这四个变量表示每次买入和卖出时的当前最大收益。
        // 因为买入时，收益是减少的，减少的收益值为“当前买入股票的价格”，
        // 所以买入时收益的初始值为整数最小值
        int profitOfFirstBuy = Integer.MIN_VALUE, profitOfFirstSell = 0;
        int profitOfSecondBuy = Integer.MIN_VALUE, profitOfSecondSell = 0;

        for (int curPrice : prices) {

            // 第一次买入时的最大收益值，因是第一次买入，所以其收益值是当前股票的负值，
            // 如果profitOfFirstBuy小于此值，则更新profitOfFirstBuy
            if (profitOfFirstBuy < -curPrice) {
                profitOfFirstBuy = -curPrice;
            }

            //第一次卖出时的最大收益值，其收益值为当前股票值加上第一次买入时的收益值，
            //即当前股票值减去第一次买入的股票值
            if (profitOfFirstSell < curPrice + profitOfFirstBuy) {
                profitOfFirstSell = curPrice + profitOfFirstBuy;
            }

            //第二次买入时的最大收益值，假使当前为第二次买入，则收益为第一次卖出时的收益加新增收益，
            //因是买入，新增收益为负。然后判断profitOfSecondBuy是否比此值小
            //若小，则更新profitOfSecondBuy，profitOfSecondBuy是记录第二次买入后收益的最大值
            if (profitOfSecondBuy < -curPrice + profitOfFirstSell) {
                profitOfSecondBuy = -curPrice + profitOfFirstSell;
            }

            // 第二次卖出时的最大收益值，第二次卖出最大收益为当前股票值加上第二次买入时的最大收益值。
            if (profitOfSecondSell < curPrice + profitOfSecondBuy) {
                profitOfSecondSell = curPrice + profitOfSecondBuy;
            }
        }

        // 因为最多可以买入两次，所以第二次卖出时的最大收益值即时所求的答案
        return profitOfSecondSell;
    }
}

因为代码的for循环中的核心代码是四条 比较值大小的判断语句，所以可以直接转换成使用Math.max()函数来进行处理，所以便有了这道题常见的求解代码：

    /**
     * 计算你能获得的最大收益
     *
     * @param prices Prices[i]即第i天的股价
     * @return 整型
     */
    public int calculateMax(int[] prices) {
        int profitOfFirstBuy = Integer.MIN_VALUE, profitOfFirstSell = 0;
        int profitOfSecondBuy = Integer.MIN_VALUE, profitOfSecondSell = 0;

        for (int curPrice : prices) {

            profitOfFirstBuy = Math.max(profitOfFirstBuy, -curPrice);
            profitOfFirstSell = Math.max(profitOfFirstSell, curPrice + profitOfFirstBuy);

            profitOfSecondBuy = Math.max(profitOfSecondBuy, 
                                              -curPrice + profitOfFirstSell);
            profitOfSecondSell = Math.max(profitOfSecondSell, 
                                              curPrice + profitOfSecondBuy);
        }
        return profitOfSecondSell;
    }

基于当前的思想，可以对这道题进行扩展，即扩展为“最多可以n次购买时股票的最大收益为题”，采用和上述同样的思想，java求解代码如下：

    /**
     * 计算你能获得的最大收益
     *
     * @param prices Prices[i]即第i天的股价
     * @param maxBuyTimes 最多的买卖次数
     * @return 整型
     */
    public int calculateMax(int[] prices, int maxBuyTimes) {
        int[] maxProfitOfBuy = new int[maxBuyTimes + 1];
        int[] maxProfitOfSell = new int[maxBuyTimes + 1];

        for (int i = 0; i <= maxBuyTimes; i++) {
            maxProfitOfBuy[i] = Integer.MIN_VALUE;
            maxProfitOfSell[i] = 0;
        }
        for (int curPrice : prices) {

            maxProfitOfBuy[0] = -curPrice;

            for (int i = 1; i <= maxBuyTimes; i++) {

                maxProfitOfBuy[i] = Math.max(maxProfitOfBuy[i], 
                                            -curPrice + maxProfitOfSell[i - 1]);

                maxProfitOfSell[i] = Math.max(maxProfitOfSell[i], 
                                            curPrice + maxProfitOfBuy[i]);
            }

        }

        return maxProfitOfSell[maxBuyTimes];
    }

注意：这个算法不保证第二次买入时间点在第一次卖出时间点之后。在迭代开始之初即在股票交易第一天，第一次买入和第二次买入均进行，而卖出则在此之后。所以计算股票收益最大值时，第n次买入的时间与第j次（j < n）次卖出的时间没有先后要求。