当前位置:   article > 正文

算法——股票买卖问题_买股票问题算法

买股票问题算法

1.无限次买卖

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
链接: leetcode.

解题思路:一次遍历,手里先握着一个价格,如果当前价格比自己高,那就卖出,添加利润,然后再买入。如果当前价格比自己低,那就直接买入。

// created by lippon
class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int n = prices.length; 
        if(n == 0) return res;
        int cur = prices[0];

        for(int i = 1; i < n; i++) {
            if(prices[i] > cur) {
                res += prices[i] - cur;
                cur = prices[i];
            } else {
                cur = prices[i];
            }
        }

        return res;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

2.只有两次买卖机会

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
链接: leetcode.

解题思路:可以将问题分解为,如果找到一个中间点,使得中间点左右两段中一次买卖的利润和最大。这样,就需要两个遍历,一个顺序一个逆序,动态规划,找到以每个元素结尾的最大利润。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n == 0) return 0;
        int[] f1 = new int[n], f2 = new int[n];
        int min = prices[0], max = prices[n - 1];


        for(int i = 1; i < n; i ++) {
            f1[i] = Math.max(f1[i - 1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }

        for(int i = n - 2; i >= 0; i --) {
            f2[i] = Math.max(f2[i + 1], max - prices[i]);
            max = Math.max(max, prices[i]);
        }

        int res = 0;
        for(int i = 0; i < n; i++) {
            res = Math.max(res, f1[i] + f2[i]);
        }

        return res;

    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

3.含有手续费

给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
添加链接描述

解题思路:利用动态规划的思想。

  • 首先是状态表示,利用一个二维数组,将当天的状态分为持有和不持有。数组值表示当天的余额。
  • 然后是状态转移,持有状态从前一天的持有状态或者当天买入转移,不持有状态从前一天的不持有状态或者当天卖出的状态转移。
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        if(n == 0) return 0;
        int cur = prices[0];
        int res  = 0;
		// 状态数组
        int[][] f = new int[n][2];
		// 第一天买入
        f[0][0] = - prices[0];

        for(int i = 1; i < n; i++) {
        	// 持有状态
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] - prices[i]);
            // 不持有状态
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] + prices[i] - fee);
        }

        return Math.max(f[n - 1][0], f[n - 1][1]);

        
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

4.含有冷冻期

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

解题思路:可以参考上一题的思路利用动态规划的思想。

  • 首先是状态标识,利用一个二维数组,将每天的状态分为持有、不持有和卖出,数组值是当天还有多少钱。不同于上一题,这里为什么需要将卖出状态拎出来呢?因为这样就能避免持有状态从前一天的卖出状态转移过来了。
  • 然后是状态转移,持有状态的前一天的只有和当天的买入状态转移,不持有的状态可能从前一天的不持有或者当天卖出转移,卖出则从前一天的持有转移。
class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int n = prices.length;
        int[][] f = new int[n][3];

        if(n == 0) return 0;

        f[0][1] = -prices[0];
        f[0][0] = 0;
        for(int i = 1; i < n; i++) {
        	// 第i天不持有股票,则前一天可能卖出了股票,也可能不持有股票
            f[i][0] = Math.max(f[i - 1][2], f[i - 1][0]);
            // 当天持有股票,则前一天可能持有股票,也可能当天买入了股票
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i]);
            // 当天卖出了股票,则前一天一定持有股票
            f[i][2] = f[i - 1][1] + prices[i];
        }

        return Math.max(f[n - 1][0], Math.max(f[n - 1][1], f[n - 1][2]));
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

5.K次买卖机会

给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
leetocde

解题思路:常规的动态规划

  1. 这里的k居然给这么大,其实超出了天数的一半就没有用,因为不会产生这么多交易;
  2. 首先是状态标识,利用一个三维数组,数组值表示当前还有多少钱,三个维度分别代表:第几天,手上是否有股票0没有1有,还有多少次买卖机会;
  3. 然后是装填转移,分为当前持有股票和不持有股票两种状态来转移分析。
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(n == 0) return 0;

        // 如果k超过了最大可买卖次数,那就将k置为最大买卖次数
        // 最大买卖次数就是天数的一半,如果当前卖出又买入,是没有意义的
        k = Math.min(k, n / 2);

        // 状态标识数组,三个维度分别代表:第几天,手上是否有股票0没有1有,还有多少次买卖机会
        // 数组值表示当前还有多少钱
        int[][][] f = new int[n][2][k + 1];
        
        // 设置初始值,第一天手上有股票的状态,就是买入第一天价格的值
        for(int i = 0; i <= k; i++) {
            f[0][1][i] = -prices[0];
        }
        // 状态转移,遍历天数
        for(int i = 1; i < n; i++) {
            // 枚举所有可能买卖次数的状态
            for(int j = 0; j <= k; j++) {
                // 当前不持有股票的状态转移
                if(j < k) {
                    // 当前不持有股票,要么前一天也没有股票,要么前一天有股票,今天卖出了
                    f[i][0][j] = Math.max(f[i - 1][0][j], f[i - 1][1][j + 1] + prices[i]);
                } else {
                    // j等于k的时候,那么说明当天没有产生交易
                    f[i][0][j] = f[i - 1][0][j];
                }

                // 当前持有股票的状态转移,要么前一天也有股票,要么当天买入了股票
                f[i][1][j] = Math.max(f[i - 1][1][j], f[i - 1][0][j] - prices[i]);
            }
        }

        int res = 0;
        // 获取最大值
        for(int i = 0; i <= k; i ++) {
            res = Math.max(res, f[n - 1][0][i]);
        }

        return res;

    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/628918
推荐阅读
相关标签
  

闽ICP备14008679号