mzoe666888

V1

2022/04/18阅读:41主题:兰青

内卷大厂系列《买卖股票的最佳时机问题四连击》

大厂高频算法面试题:《买卖股票的最佳时机系列》,现实生活中的股票可不是这么玩的,所有题都是基于股票价格已知的情况下,做最优选择,属于事后诸葛亮,通过股票问题,您将学到动态规划及通过斜率优化省掉枚举行为等技巧。

一、买卖股票的最佳时机 I

给定一个数组 prices ,它的第 i 个元素prices[i]表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票,并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回0 。

示例 1

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2

输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0

leetcode

1、分析

股票问题I,只能做一次交易,股票最终是以某天卖出去,假设每天卖出去都能获取的最大利润,求max就是最终获取的最大利润,怎么求最大利润,之前天的股票以最低价格买入,当天卖出去的价格减去最低买入的价就是当天获取的最大利润。

2、实现

public static int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }
    // 0...i 最小值
    int min = prices[0];
    int ans = 0;
    for (int i = 1; i < prices.length; i++) {
        min = Math.min(min, prices[i]);
        ans = Math.max(ans, prices[i] - min);
    }
    return ans;
}

二、买卖股票的最佳时机 II

给定一个数组 prices ,其中 prices[i] 表示股票第 i 天的价格。

在每一天,你可能会决定购买或出售股票。你在任何时候最多只能持有一股股票。你也可以购买它,然后在同一天出售。

返回你能获得的最大利润 。

示例 1:

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

示例 2:

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0

leetcode

1、分析

股票问题II,能做多次交易,但只能同时拥有一只股票。在买入股票时,如果手里存在股票,必须卖了之前的股票,才有资格买入当前股票。

看着题目规定的条件还挺复杂,仔细想想其实就是在求股票折线图上有多少上升区间,把所有折线上升的区间都累加起来就是最终获取的最大利润。

怎么求上升区间?很简单,只要 arr[i] > arr[i-1] 就是上升区间

2、实现

public static int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }
    int ans = 0;
    for (int i = 1; i < prices.length; i++) {
        ans += Math.max(prices[i] - prices[i - 1], 0);
    }
    return ans;
}

三、买卖股票的最佳时机 III

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

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

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

示例 1:

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

示例 2

输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。   
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3

输入:prices = [7,6,4,3,1
输出:0 
解释:在这个情况下, 没有交易完成, 所以最大利润为 0

示例 4

输入:prices = [1]
输出:0

leetcode

1、分析

股票问题III,只能做2次交易,如果按照股票问题II那样处理,把2次上升区间获得的利润加起来,不一定就是获得的最大利润。

一定要以i号时间点两次交易做完,并且第二次的卖出时机在i位置,第二次的买入时机,揉进到了第一次最好收益后,再减去第二次买入开销,当来到i位置时,只需要加上这个第二次的收益就是最终整体最好的收益

doneOnceMinusBuyMax,0~i位置最优:

  • 可能性一:第二次在i位置上没买入,在0~i-1范围上发生了第二次买入,那么i位置上的最优就是0~i-1范围上的最优doneOnceMinusBuyMax
  • 可能性二:第二次在i位置上买入,那么最优就是之前产生的最大doneOnceMax减去第二次买入的价格

2、实现

public static int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    int ans = 0;
    // doneOnceMinusBuyMax:(第一次交易完 - 第二次买入)的最大利润
    int doneOnceMinusBuyMax = -prices[0];
    int doneOnceMax = 0;// 0 : [0] - [0]
    int min = prices[0];
    for (int i = 1; i < prices.length; i++) {
        ans = Math.max(ans, doneOnceMinusBuyMax + prices[i]);
        min = Math.min(min, prices[i]);
        doneOnceMax = Math.max(doneOnceMax, prices[i] - min);
        // 两种可能性:1、i位置第二次不买 2、i位置第二次买
        doneOnceMinusBuyMax = Math.max(doneOnceMinusBuyMax, doneOnceMax - prices[i]);
    }
    return ans;
}

四、买卖股票的最佳时机 IV

给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

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

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

示例 1

输入:k = 2, prices = [2,4,1]
输出:2
解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。

示例 2

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

leetcode

1、分析

股票问题IV,最多能交易K次,上升的次数最多2/N次,下降的次数最多2/N次,上升下降,上升下降,所以有这个结论。

如果K > N/2,那么就是无限次交易,就是买卖股票问题 II

如果K < N/2,利用动态规划求解,属于样本对应模型,一个样本做行,一个样本做列,arr[0...i]上的股票做行,0~K次做列。

dp[i][j]含义:只能在arr[0...i]上做交易,交易次数不超过j次,做大收益是什么?

第一行格子怎么填? dp[0][j] = 0,代表只能选0号股票,买入和卖出,发生0次,1次,2次,...,j次,所以产生的利润永远为0

第一列格子怎么填? dp[i][0] = 0,代表不管怎么选股票,交易次数都是0次,那就是不买也不卖,所以产生的利润永远为0

其余格子怎么填? dp[i][j] = ? 分析可能性如下:

  • 可能性一:i位置不参与任何易,只要保证0~i-1上参与 j 次交易即可,所以 dp[i][j] = dp[i-1][j]
  • 可能性二:i位置参与交易,但不能让i位置参与前几次交易,如果i位置参与前几次交易,那么后几次交易都是废的,买入和卖出产生的利润为0,i位置参与最后一次交易的卖出时机,分析可能性如下:
    • ① 最后一次的买入时机是i位置
    • ② 最后一次的买入时机是i-1位置
    • ③ 最后一次的买入时机是i-2位置
    • ...
    • ? 最后一次的买入时机是0位置

dp[i][j] = max(dp[i-1][j], max(dp[k][j-1] + arr[i] - arr[k])), 0 ≤ k ≤ i

2、实现

2.2、方法一

public static int maxProfit(int K, int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    if (K >= N / 2) {
        return allTrans(arr);
    }
    // dp[0][...] = 0 第一行
    // dp[...][0] = 0 第一列
    int[][] dp = new int[N][K + 1];
    for (int i = 1; i < N; i++) { // 其余格子
        for (int j = 1; j <= K; j++) {
            // 1) [i] 不参与 dp[i-1][j]
            dp[i][j] = dp[i - 1][j];
            // 2) 枚举,能否推高dp[i][j]
            // dp[p][k-1] + [i] - [p]
            for (int p = 0; p <= i; p++) { // 枚举行为
                dp[i][j] = Math.max(dp[p][j - 1] + arr[i] - arr[p], dp[i][j]);
            }
        }
    }
    return dp[N - 1][K];
}

// 所有交易,也就是股票问题II
public static int allTrans(int[] prices) {
    int ans = 0;
    for (int i = 1; i < prices.length; i++) {
        ans += Math.max(prices[i] - prices[i - 1], 0);
    }
    return ans;
}

2.3、方法二

发现方法一有枚举行为(最内层循环),可以通过斜率优化省掉最里边的循环。

dp[i][j]能推出dp[i+1][j],所以剩下的格子不是从左往右填,而是从上往下填。

每列每列的填,每列上在一行一行的填一个格子。

public static int maxProfit(int K, int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }
    int N = prices.length;
    if (K >= N / 2) {
        return allTrans(prices);
    }
    int[][] dp = new int[N][K + 1];
    int ans = 0;
    for (int j = 1; j <= K; j++) {
        int t = dp[0][j - 1] - prices[0];
        for (int i = 1; i < N; i++) {
            t = Math.max(t, dp[i][j - 1] - prices[i]);
            dp[i][j] = Math.max(dp[i - 1][j], t + prices[i]);
            ans = Math.max(ans, dp[i][j]);
        }
    }
    return ans;
}

// 所有交易,也就是股票问题II
public static int allTrans(int[] prices) {
    int ans = 0;
    for (int i = 1; i < prices.length; i++) {
        ans += Math.max(prices[i] - prices[i - 1], 0);
    }
    return ans;
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1