714. 买卖股票的最佳时机含手续费(中等)

Posted on In Views:

1，问题描述

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

难度：中等

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

1
2
3
4
5
6
7
8
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

1
2
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

  • 1 <= prices.length <= 5 * 10^4
  • 1 <= prices[i] < 5 * 10^4
  • 0 <= fee < 5 * 10^4

2，初步思考

​ 我自己第一次没有解出来

​ 动态规划算法、贪心算法2种

3，代码处理

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
public class _714买卖股票的最佳时机含手续费 {

    public int maxProfit_greedy_gov(int[] prices, int fee) {
        int len = prices.length;
        int buy = prices[0] + fee;
        int profit = 0;
        for (int i = 1; i < len; i++) {
            if (prices[i] + fee < buy) {// 替换为新的最小的
                buy = prices[i] + fee;
            } else if (prices[i] > buy) {// 可以进行销售
                profit += prices[i] - buy;
                buy = prices[i];// 没有设置手续费，表示可以反悔
            }
        }
        return profit;
    }


    // 贪心算法，这里不限制次数了！！！只要不亏就买卖(错误解答)
    public int maxProfit_greedy(int[] prices, int fee) {
        int minCur = prices[0];
        int maxCur = prices[0];
        int len = prices.length, sum = 0, sumCur = 0;
        for (int i = 1; i < len; i++) {
            if (prices[i] > maxCur) {
                maxCur = prices[i];
            } else if (prices[i] < maxCur) {
                sumCur = maxCur - minCur - fee;
                if (sumCur <= 0) {
                    minCur = Math.min(minCur, prices[i]);
                    continue;
                }
                sum += Math.max(sumCur, 0);
                minCur = prices[i];
                maxCur = prices[i];
            }
        }
        sumCur = maxCur - minCur - fee;
        sum += Math.max(sumCur, 0);
        return sum;
    }

    // 官方解法，dp
    public int maxProfit_dp_gov(int[] prices, int fee) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }
    public int maxProfit_dp_gov_v2(int[] prices, int fee) {
        int len = prices.length;
        int sell = 0,buy = -prices[0];
        for (int i = 1; i < len; i++) {
            sell = Math.max(sell, buy + prices[i] - fee);
            buy = Math.max(buy, sell - prices[i]);
        }
        return sell;
    }

    public int maxProfit_dp(int[] prices, int fee) {
        int len = prices.length;
        int kLen = len * 2;
        int[] dp = new int[kLen];
        for (int i = 0; i < kLen; i += 2) {
            dp[i] = -prices[0];
            dp[i + 1] = 0;
        }
        for (int i = 1; i < len; i++) {
            int temp = dp[kLen - 1];
            dp[0] = Math.max(dp[0], -prices[i]);
            dp[1] = Math.max(dp[1], dp[0] + prices[i] - fee);
            for (int j = 2; j < kLen; j += 2) {
                dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);
                dp[j + 1] = Math.max(dp[j + 1], dp[j] + prices[i] - fee);
            }
            if (temp == dp[kLen - 1]) break;
        }
        return dp[kLen - 2];
    }

    // 暴力求解，依次计算1～n次的最大值，求最大数(超时)
    public int maxProfit_brute(int[] prices, int fee) {
        int k = 0;
        int max = Integer.MIN_VALUE;
        int maxCur = 0;
        while (k <= prices.length / 2) {
            maxCur = maxProfit_k(k, prices) - fee * k;
            if (maxCur > max) {
                max = maxCur;
            } else {
                break;
            }
            k++;
        }
        return max;
    }

    public int maxProfit_k(int k, int[] prices) {
        if (k == 0) return 0;
        int len = prices.length;
        int kLen = k * 2;
        int[] dp = new int[kLen];
        for (int i = 0; i < kLen; i += 2) {
            dp[i] = -prices[0];
            dp[i + 1] = 0;
        }
        for (int i = 1; i < len; i++) {
            dp[0] = Math.max(dp[0], -prices[i]);
            dp[1] = Math.max(dp[1], dp[0] + prices[i]);
            for (int j = 2; j < kLen; j += 2) {
                dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);
                dp[j + 1] = Math.max(dp[j + 1], dp[j] + prices[i]);
            }
        }
        return dp[k * 2 - 1];
    }

    public static void main(String[] args) {
        _714买卖股票的最佳时机含手续费 test = new _714买卖股票的最佳时机含手续费();
//        System.out.println(test.maxProfit_greedy(new int[]{1,3,2,8,4,9}, 2));
        System.out.println(test.maxProfit_greedy_gov(new int[]{1, 3, 2, 8, 4, 9}, 2));
        System.out.println(test.maxProfit_greedy_gov(new int[]{1, 3, 2, 8, 4, 9}, 2));
    }
}

4，参考链接

wqs二分优秀做法