LWC 55:714. Best Time to Buy and Sell Stock with Transaction Fee

LWC 55:714. Best Time to Buy and Sell Stock with Transaction Fee

传送门:714. Best Time to Buy and Sell Stock with Transaction Fee

Problem:

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.) Return the maximum profit you can make.

Example 1:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by:

  • Buying at prices[0] = 1
  • Selling at prices[3] = 8
  • Buying at prices[4] = 4
  • Selling at prices[5] = 9

The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

0 < prices.length <= 50000.

0 < prices[i] < 50000.

0 <= fee < 50000.

思路: 动态规划,对于每一个可能的买入点都有三种状态:买,卖,什么都不做,枚举出这些状态的组合,求最大profit即可。

目标:

  • 前i天的持有股票数最大,记为:hold[i]
  • 前i天的股票利益最大,记为:unHold[i]

状态转移:

对于第i + 1天,三种状态,买,卖,什么都不做。

买: hold[i] = max{unHold[i] - prices[i + 1] - fee, hold[i - 1]; 卖:unHold[i] = max{hold[i] + prices[i + 1], unHold[i - 1];

代码如下:

     public int maxProfit(int[] prices, int fee) {
         int n = prices.length;
         int[] hold   = new int[n + 1];
         int[] unHold = new int[n + 1];

         hold[0] = Integer.MIN_VALUE;

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

         return unHold[n];
     }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P3128 [USACO15DEC]最大流Max Flow(树上差分)

边差分就是对边进行操作,我们在$u, v$除加上$val$,同时在$lca$处减去$2 * val$

573
来自专栏武培轩的专栏

迅雷2019秋招后台开发编程题题解

有红黑两种颜色的方块积木,红色代表正数A,黑色代表负数B。选出17块积木排成一排,使得任意相邻7块积木之和都小于0。如何挑选才能使17块积木之和最大,最大值是多...

872
来自专栏用户2442861的专栏

2014美团网笔试题目(总结)

http://blog.csdn.net/wzy_1988/article/details/12438143

341
来自专栏wym

2013年多校赛 hdu4607

   那么就考虑树上最长距离,树的直径, 如果访问的点大于树的直径就要走回头路,答案即多的数乘2加上原来树的直径

1025
来自专栏技术与生活

设计模式-备忘录模式

备忘录角色对如何其他对象提供一个接口,也就是宽接口的话,那么备忘录角色存储的内部状态都暴露给其他对象。这种情况导致发起人的状态都没看到,是破坏封装性的,只能通过...

772
来自专栏数据结构与算法

洛谷P1437 [HNOI2004]敲砖块(dp)

在一个凹槽中放置了 n 层砖块、最上面的一层有n 块砖,从上到下每层依次减少一块砖。每块砖

782
来自专栏静默虚空的博客

JAVA 设计模式 备忘录模式

用途 备忘录模式 (Memento) 在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态。 这样以后就可将该对象恢复到原先保存的状态...

1828
来自专栏Golang语言社区

【转载】用队列求解迷宫最短路径及其应用(围住神经猫)

问题 给定一个M×N的迷宫图,求一条从指定入口到出口的最短路径.假设迷宫图如图所示(M=8, N=8) ? 对于图中的每个方块,空白表示通道,阴影表示墙。所...

3257
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

1678
来自专栏云霄雨霁

数据压缩----游程编码

1400

扫码关注云+社区