算法题买卖股票的最佳时机含手续费-程序员充电站

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

问题描述

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

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

返回获得利润的最大值。

注意：这里的一笔交易指买入股票然后卖出股票的整个过程。

示例：

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2 输出: 8 解释: 能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 交易利润: 8 - 1 - 2 = 5 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 交易利润: 9 - 4 - 2 = 3 总利润: 5 + 3 = 8 输入: prices = [1,3,7,5,10,3], fee = 3 输出: 6 解释: 最优策略是买入1，卖出10，利润: 10-1-3=6

算法思路

核心思想：

每一天只有两种状态：

持有股票（hold）：手上持有一股股票
不持有股票（sold）：手上没有股票

状态转移方程：

持有状态（hold）：
- 要么之前就持有，今天继续持有：hold = hold
- 要么今天买入：hold = sold - price[i]
- 取最大值：hold = max(hold, sold - price[i])
不持有状态（sold）：
- 要么之前就不持有，今天继续不持有：sold = sold
- 要么今天卖出（需要支付手续费）：sold = hold + price[i] - fee
- 取最大值：sold = max(sold, hold + price[i] - fee)

初始化：

第一天持有：hold = -prices[0]（买入股票）
第一天不持有：sold = 0（什么也不做）

结果：

最后一天不持有股票的状态：sold
因为持有股票肯定不如卖出后获得现金

代码实现

方法一：动态规划

classSolution{/** * 计算含手续费的股票交易最大利润 * * @param prices 股票价格数组 * @param fee 交易手续费 * @return 最大利润 */publicintmaxProfit(int[]prices,intfee){if(prices==null||prices.length<=1){return0;}// 初始化状态inthold=-prices[0];// 持有股票的最大利润intsold=0;// 不持有股票的最大利润// 从第二天开始遍历for(inti=1;i<prices.length;i++){// 保存前一天的hold状态，因为会被更新intprevHold=hold;// 更新持有状态：继续持有 或 买入股票hold=Math.max(hold,sold-prices[i]);// 更新不持有状态：继续不持有 或 卖出股票（支付手续费）sold=Math.max(sold,prevHold+prices[i]-fee);}// 最终状态是不持有股票returnsold;}}

方法二：优化

classSolution{/** * 直接使用变量更新，无需额外空间 */publicintmaxProfit(int[]prices,intfee){if(prices.length<=1){return0;}inthold=-prices[0];intsold=0;for(inti=1;i<prices.length;i++){// 这里需要先计算新的sold，再更新holdintnewHold=Math.max(hold,sold-prices[i]);intnewSold=Math.max(sold,hold+prices[i]-fee);hold=newHold;sold=newSold;}returnsold;}}

算法分析

时间复杂度：O(n)，n是价格数组的长度，只需要遍历一次
空间复杂度：O(1)，只使用常数个额外变量

算法过程

1：prices = [1,3,7,5,10,3], fee = 3

过程：

第0天：hold=-1, sold=0
第1天：hold=-1, sold=max(0, -1+3-3)=0
第2天：hold=-1, sold=max(0, -1+7-3)=3
第3天：hold=max(-1, 3-5)=-1, sold=3
第4天：hold=-1, sold=max(3, -1+10-3)=6
第5天：hold=max(-1, 6-3)=3, sold=6

最终结果：6

测试用例

publicclassTestMaxProfit{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例1int[]prices1={1,3,2,8,4,9};intfee1=2;System.out.println("Test 1: "+solution.maxProfit(prices1,fee1));// 8// 测试用例2：标准示例2int[]prices2={1,3,7,5,10,3};intfee2=3;System.out.println("Test 2: "+solution.maxProfit(prices2,fee2));// 6// 测试用例3：单天int[]prices3={1};intfee3=1;System.out.println("Test 3: "+solution.maxProfit(prices3,fee3));// 0// 测试用例4：两天，无利润int[]prices4={5,4};intfee4=1;System.out.println("Test 4: "+solution.maxProfit(prices4,fee4));// 0// 测试用例5：两天，有利润int[]prices5={1,5};intfee5=2;System.out.println("Test 5: "+solution.maxProfit(prices5,fee5));// 2 (5-1-2=2)// 测试用例6：手续费很高int[]prices6={1,5,10};intfee6=10;System.out.println("Test 6: "+solution.maxProfit(prices6,fee6));// 0// 测试用例7：递增序列int[]prices7={1,2,3,4,5};intfee7=1;System.out.println("Test 7: "+solution.maxProfit(prices7,fee7));// 3 (5-1-1=3)// 测试用例8：递减序列int[]prices8={5,4,3,2,1};intfee8=1;System.out.println("Test 8: "+solution.maxProfit(prices8,fee8));// 0}}