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 条评论
登录 后参与评论

相关文章

来自专栏ml

暑假集训之专题----拓扑排序题解

第一单: Problem A Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/3276...

2775
来自专栏ml

HDU----(3294)Girls' research(manacher)

Girls' research Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3...

2605
来自专栏ml

HDUOJ------Worm

Worm Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

3328
来自专栏算法修养

Code Forces 21 A(模拟)

A. Jabber ID time limit per test 0.5 second memory limit per test 256 mega...

3018
来自专栏Bingo的深度学习杂货店

Q122 Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on...

3255
来自专栏算法修养

HOJ 2133&POJ 2964 Tourist(动态规划)

Tourist Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1503...

3348
来自专栏Android 开发学习

ConstraintLayout 使用简介一 背景二 demo三 进一步升级打怪四 更多

4514
来自专栏郭耀华‘s Blog

LeetCode第二天&第三天

leetcode 第二天 2017年12月27日 4.(118)Pascal's Triangle ? JAVA class Solution { pu...

27612
来自专栏哲学驱动设计

Sort By Double

I have wrote a article which describes how to deal with a complicate data struct...

1907
来自专栏calmound

UVA 10604 Chemical Reaction(六维dp数组)

题意:有六种不同的试剂,放于试管中,不同的试剂融合其产生的热量不同,且生成的新试剂也不相同,问最后最低温度是多少。 分析:由于只有六种试剂,所以开辟一个六维dp...

3287

扫码关注云+社区