买卖股票的最佳时机系列问题

作者:Grey

原文地址:买卖股票的最佳时机系列问题

LeetCode 121. 买卖股票的最佳时机

主要思路:因为只有一股可以交易,所以我们可以枚举必须以i位置作为卖出时机的情况下,得到的最大收益是多少。如果我们得到每个i位置的最大收益,那么最大收益必是所有位置的最大收益的最大值

使用两个变量:

min变量:表示遍历到的位置之前的最小值是什么。

max变量:表示当前收集到必须以i位置卖出的最大收益是多少。

遍历数组一遍,在遍历到i位置的时候,minmax的更新逻辑如下:

min = Math.min(arr[i], min); // 每次遍历到的arr[i]和全局min进行比较,看能否刷新min的值
max = Math.max(arr[i] - min, max); // arr[i] - min 表示必须以i位置卖出时候的最大收益是什么,和全局的max值pk的最大值赋予max

遍历完数组,返回max的值就是最终答案。完整代码见:

public class LeetCode_0121_BestTimeToBuyAndSellStock {
    public int maxProfit(int[] arr) {
        int max = 0;
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            min = Math.min(arr[i], min);
            max = Math.max(arr[i] - min, max);
        }
        return max;
    }
}

LeetCode 122. 买卖股票的最佳时机 II

主要思路:由于可以进行任意次的交易,但是任何时候最多只能持有一股股票,所以我们可以把股票曲线的所有上升段都抓取到,累加收益就是最大收益。遍历数组,遍历到的位置减去前一个位置的值,如果是正数,就收集,如果是负数,就把本次收益置为0(就等于没有做这次交易),这样遍历一遍数组,就不会错过所有的收益。

设置一个变量max,初始为0,用于收集最大收益值,来到i位置,max更新逻辑如下:

max += Math.max((prices[i] - prices[i - 1]), 0);

完整代码如下:

public int maxProfit(int[] prices) {
   int max = 0;
   for (int i = 1; i < prices.length; i++) {
        // 把所有上坡都给抓到
        max += Math.max((prices[i] - prices[i - 1]), 0);
   }
   return max;
}

由本题可以简单得出一个结论:如果数组元素个数为N,则最多执行N/2次交易就可以抓取所有的上升段的值(极端情况下,当前时刻买,下一个时刻卖,保持这样的交易一直到最后,执行的交易次数就是N/2

LeetCode 188. 买卖股票的最佳时机 IV

主要思路:

  1. 如果k的值大于等于数组长度的二分之一,就等于有无限次交易,在这样的情况下,可以直接用问题二的解法来做。
  2. 如果k的值小于数组长度的二分之一,就需要单独考虑了。

在第2种情况下,我们定义

int[][] dp = new int[N][k+1]

其中dp[i][j]表示[0...i]范围内交易j次获得的最大收益是多少。如果可以把dp这个二维表填好,那么返回dp[N-1][k]的值就是题目要的答案。

dp这个二维矩阵中,

第一行的值表示数组[0..0]范围内,交易若干次的最大收益,显然,都是0。

第一列的值表示数组[0...i]范围内,交易0次获得的最大收益,显然,也都是0。

针对任何一个普遍位置dp[i][j]的值,

我们可以枚举i位置是否参与交易,如果i位置不参与交易,那么dp[i][j] = dp[i-1][j],如果i位置参与交易,那么i位置一定是最后一次的卖出时机。

那最后一次买入的时机,可以是如下情况:

最后一次买入的时机在i位置,那么dp[i][j] = dp[i][j-1] - arr[i] + arr[i]

最后一次买入的时机在i-1位置,那么dp[i][j] = dp[i-1][j-1] - arr[i-1] + arr[i]

最后一次买入的时机在i-2位置,那么dp[i][j] = dp[i-2][j-1] - arr[i-2] + arr[i]

最后一次买入的时机在0位置,那么dp[i][j] = dp[0][j-1] - arr[0] + arr[i]

// i位置不参与交易,则dp[i][j]至少是dp[i-1][j]
dp[i][j] = dp[i - 1][j];
for (int m = 0; m <= i; m++) {
    // 枚举每次买入的时机
    dp[i][j] = Math.max(dp[m][j - 1] - arr[m] + arr[i] , dp[i][j]);
}

完整代码如下:

public class LeetCode_0188_BestTimeToBuyAndSellStockIV {
    public static int maxProfit(int k, int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int N = arr.length;
        if (k >= N >> 1) {
            return infinityMax(arr);
        }
        int[][] dp = new int[N][k + 1];
        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= k; j++) {
                // i位置不参与交易,则dp[i][j]至少是dp[i-1][j]
                dp[i][j] = dp[i - 1][j];
                for (int m = 0; m <= i; m++) {
                    // 枚举每次买入的时机
                    dp[i][j] = Math.max(dp[m][j - 1] - arr[m] + arr[i], dp[i][j]);
                }
            }
        }
        return dp[N - 1][k];
    }


    public static int infinityMax(int[] arr) {
        int ans = 0;
        for (int i = 1; i < arr.length; i++) {
            ans += Math.max(arr[i] - arr[i - 1], 0);
        }
        return ans;
    }
}


上述代码中包含一个枚举行为

dp[i][j] = dp[i - 1][j] + arr[i] - arr[i];
for (int m = 0; m <= i; m++) {
   // 枚举每次买入的时机
   dp[i][j] = Math.max(dp[m][j - 1] - arr[m] + arr[i], dp[i][j]);
}

增加了时间复杂度,我们可以优化这个枚举。

我们可以举一个具体的例子来说明如何优化,

比如,

当我们求dp[5][3]这个值,我们可以枚举5位置是否参与交易,假设5位置不参与交易,那么dp[5][3] = dp[4][3],假设5位置参与交易,那么5位置一定是最后一次的卖出时机。那最后一次买入的时机,可以是如下情况:

最后一次买入的时机在5位置,那么dp[5][3] = dp[5][2] - arr[5] + arr[5]

最后一次买入的时机在4位置,那么dp[5][3] = dp[4][2] - arr[4] + arr[5]

最后一次买入的时机在3位置,那么dp[5][3] = dp[3][2] - arr[3] + arr[5]

最后一次买入的时机在2位置,那么dp[5][3] = dp[2][2] - arr[2] + arr[5]

最后一次买入的时机在1位置,那么dp[5][3] = dp[1][2] - arr[1] + arr[5]

最后一次买入的时机在0位置,那么dp[5][3] = dp[0][2] - arr[0] + arr[5]

我们求dp[4][3]这个值,我们可以枚举4位置是否参与交易,假设4位置不参与交易,那么dp[4][3] = dp[3][3],假设4位置参与交易,那么4位置一定是最后一次的卖出时机。那最后一次买入的时机,可以是如下情况:

最后一次买入的时机在4位置,那么dp[4][3] = dp[4][2] - arr[4] + arr[4]

最后一次买入的时机在3位置,那么dp[4][3] = dp[3][2] - arr[3] + arr[4]

最后一次买入的时机在2位置,那么dp[4][3] = dp[2][2] - arr[2] + arr[4]

最后一次买入的时机在1位置,那么dp[4][3] = dp[1][2] - arr[1] + arr[4]

最后一次买入的时机在0位置,那么dp[4][3] = dp[0][2] - arr[0] + arr[4]

比较dp[5][3]dp[4][3]的依赖关系,可以得到如下结论:

假设在求dp[4][3]的过程中,以下递推式的最大值我们可以得到

dp[4][2] - arr[4]

dp[3][2] - arr[3]

dp[2][2] - arr[2]

dp[1][2] - arr[1]

dp[0][2] - arr[0]

我们把以上式子的最大值定义为best,那么

dp[5][3] = Math.max(dp[4][3],Math.max(dp[5][2] - arr[5] + arr[5], best + arr[5]))

所以dp[5][3]可以由dp[4][3]加速得到,

同理,

dp[4][3]可以通过dp[3][3]加速得到,

dp[3][3]可以通过dp[2][3]加速得到,

dp[2][3]可以通过dp[1][3]加速得到,

dp[1][3]可以很简单得出,dp[1][3]有如下几种可能性:

可能性1,1位置完全不参与,则

int p1 = dp[0][3]

可能性2,1位置作为最后一次的卖出时机,买入时机是1位置

int p2 = dp[1][2] + arr[1] - arr[1]

可能性3,1位置作为最后一次的卖出时机,买入时机是0位置

int p3 = dp[0][2] + arr[1] - arr[0]

此时,best的值为

int best = Math.max(p2 - arr[1], p3 - arr[1])

然后通过dp[1][3]加速dp[2][3],通过dp[2][3]加速dp[3][3]……,所以二维dp的填写方式是按列填,

先填dp[1][0]dp[1][2]一直到dp[1][k],填好第一列;

然后填dp[2][0],dp[2][1]一直到dp[2][k],填好第二列;

依次填好每一列,直到填完第N-1列。

枚举行为被优化,优化枚举后的完整代码如下:

public class LeetCode_0188_BestTimeToBuyAndSellStockIV {

    public static int maxProfit(int k, int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int N = arr.length;
        if (k >= N >> 1) {
            return infinityMax(arr);
        }
        int[][] dp = new int[N][k + 1];
        for (int j = 1; j <= k; j++) {
            int p1 = dp[0][j];
            int best = Math.max(dp[1][j - 1] - arr[1], dp[0][j - 1] - arr[0]);
            dp[1][j] = Math.max(p1, best + arr[1]);
            for (int i = 2; i < N; i++) {
                p1 = dp[i - 1][j];
                best = Math.max(dp[i][j - 1] - arr[i], best);
                dp[i][j] = Math.max(p1, best + arr[i]);
            }
        }
        return dp[N - 1][k];
    }

    public static int infinityMax(int[] arr) {
        int ans = 0;
        for (int i = 1; i < arr.length; i++) {
            ans += Math.max(arr[i] - arr[i - 1], 0);
        }
        return ans;
    }
}

LeetCode 123. 买卖股票的最佳时机 III

主要思路:上一个问题中,令k=2就是本题的答案。

LeetCode 309. 最佳买卖股票时机含冷冻期

主要思路:因为有了冷冻期,所以每个位置的状态有如下三种:

  1. 冷冻期

  2. 持有股票

  3. 不持有股票,不在冷冻期

定义三个数组,分别表示i位置这三种情况下的最大值是多少

// 处于冷冻期
int[] cooldown = new int[N];
// 持有股票
int[] withStock = new int[N];
// 不持有股票,也不处于冷冻期
int[] noStock = new int[N];

显然有如下结论:

// 0位置需要处于冷冻期,说明0位置买了又卖掉,收益是0
cooldown[0] = 0; 
// 0位置需要持有股票,只有可能在0位置买了一股,这个时候收益为0-arr[0]
withStock[0] = -arr[0];
// 0位置没有股票,也不在冷冻期,说明在0位置就没有做任何决策。此时收益也是0
noStock[0] = 0;

针对一个普遍位置i

// 如果i位置要处于冷冻期,那么前一个位置必须持有股票,且在当前位置卖掉,处于cooldown状态
cooldown[i] = withStock[i - 1] + arr[i];
// 如果i位置要持有股票,那么前一个位置可以持有股票,到当前位置不做决策,或者前一个位置没有股票,当前位置买入一股
withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);
// 如果i位置没有股票,那么前一个位置可能也没股票,或者前一个位置是冷冻期,到当前位置也没有进行买入动作
noStock[i] = Math.max(noStock[i - 1], cooldown[i - 1]);

最大收益就是如上三种方式的最大值。完整代码见:

public class LeetCode_0309_BestTimeToBuyAndSellStockWithCooldown {
    public static int maxProfit(int[] arr) {
        if (arr.length < 2) {
            return 0;
        }
        int N = arr.length;
        // 处于冷冻期
        int[] cooldown = new int[N];
        // 持有股票
        int[] withStock = new int[N];
        // 不持有股票,也不处于冷冻期
        int[] noStock = new int[N];
        cooldown[0] = 0;
        withStock[0] = -arr[0];
        noStock[0] = 0;
        for (int i = 1; i < arr.length; i++) {
            withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);
            cooldown[i] = withStock[i - 1] + arr[i];
            noStock[i] = Math.max(noStock[i - 1], cooldown[i - 1]);
        }
        return Math.max(cooldown[N - 1], Math.max(withStock[N - 1], noStock[N - 1]));
    }
}

由于三个数组有递推关系,所以可以用三个变量替换三个数组,做空间压缩,优化后的代码如下:

public class LeetCode_0309_BestTimeToBuyAndSellStockWithCooldown {
   
    // 空间压缩版本
    public static int maxProfit(int[] arr) {
        if (arr.length < 2) {
            return 0;
        }
        // 处于冷冻期
        int cooldown = 0;
        // 持有股票
        int withStock = -arr[0];
        // 不持有股票,也不处于冷冻期
        int noStock = 0;

        for (int i = 1; i < arr.length; i++) {
            int next1 = Math.max(withStock, noStock - arr[i]);
            int next2 = withStock + arr[i];
            int next3 = Math.max(noStock, cooldown);
            withStock = next1;
            cooldown = next2;
            noStock = next3;
        }
        return Math.max(cooldown, Math.max(withStock, noStock));
    }
}

LeetCode 714. 买卖股票的最佳时机含手续费

主要思路:由于没有冷冻期,所以在i位置的时候,状态只有两种

// withStock[i]表示:i位置有股票的状态下,最大收益
int[] withStock = new int[arr.length];
// noStock[i]表示:i位置没有股票的状态下,最大收益
int[] noStock = new int[arr.length];

针对0位置

// 0位置持有股票,最大收益,只可能是0位置买入一股
withStock[0] = -arr[0];
// 0位置不持有股票,最大收益,只能是0位置不做交易,收益为0,如果0位置做交易,收益就是(0 - arr[i] + arr[i] - fee),显然小于0
noStock[0] = 0;

针对普遍位置i

// i位置需要有股票,说明i位置的股票可以是i-1位置到现在不交易获得的,也可以是i-1位置没有股票,买下当前这一股获得的
withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);
// i位置没有股票,说明i位置的股票可以由i-1位置上有股票的状态到当前位置卖出一股(含手续费),也可以是沿用上一个位置没有股票的最大收益
noStock[i] = Math.max(withStock[i - 1] + arr[i] - fee, noStock[i - 1]);

完整代码如下:

public class LeetCode_0714_BestTimeToBuyAndSellStockWithTransactionFee {
    public static int maxProfit1(int[] arr, int fee) {
        if (arr.length < 2) {
            return 0;
        }
        int[] withStock = new int[arr.length];
        int[] noStock = new int[arr.length];
        // 持有股票
        withStock[0] = -arr[0];
        // 不持有股票
        noStock[0] = 0;
        for (int i = 1; i < arr.length; i++) {
            withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);
            noStock[i] = Math.max(withStock[i - 1] + arr[i] - fee, noStock[i - 1]);
        }
        return Math.max(withStock[arr.length - 1], noStock[arr.length - 1]);
    }
}

同样的,两个数组都有递推关系,可以做空间压缩,简化后的代码如下:

public class LeetCode_0714_BestTimeToBuyAndSellStockWithTransactionFee {

    public static int maxProfit(int[] arr, int fee) {
        if (arr.length < 2) {
            return 0;
        }
        // 持有股票
        int withStock = -arr[0];
        // 不持有股票
        int noStock = 0;
        for (int i = 1; i < arr.length; i++) {
            int next1 = Math.max(withStock, noStock - arr[i]);
            int next3 = Math.max(withStock + arr[i] - fee, noStock);
            withStock = next1;
            noStock = next3;
        }
        return Math.max(withStock, noStock);
    }
}

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云

 3 total views,  1 views today

页面下部广告