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

相关文章

来自专栏武培轩的专栏

Leetcode#867. Transpose Matrix(转置矩阵)

1163
来自专栏AI研习社

从 Encoder 到 Decoder 实现 Seq2Seq 模型

前言 好久没有更新专栏,今天我们来看一个简单的Seq2Seq实现,我们将使用TensorFlow来实现一个基础版本的Seq2Seq,主要帮助理解Seq2Se...

56513
来自专栏李智的专栏

Deep learning基于theano的keras学习笔记(1)-Sequential模型

《统计学习方法》中指出,机器学习的三个要素是模型,策略和优算法,这当然也适用于深度学习,而我个人觉得keras训练也是基于这三个要素的,先建立深度模型,然后选用...

911
来自专栏小鹏的专栏

Tensorflow使用的预训练的resnet_v2_50,resnet_v2_101,resnet_v2_152等模型预测,训练

tensorflow 实现:Inception,ResNet , VGG , MobileNet, Inception-ResNet; 地址: https:/...

8888
来自专栏我是业余自学C/C++的

对角矩阵

1062
来自专栏数说工作室

函数玩一玩 | 【SAS Says·扩展篇】IML:2.函数

【SAS Says·扩展篇】IML 分6集,回复【SASIML】查看全部: 入门 | SAS里的平行世界 函数 | 函数玩一玩 编程 | IML的条件与循环 模...

3609
来自专栏决胜机器学习

从机器学习学python(四) ——numpy矩阵基础

从机器学习学python(四)——numpy矩阵基础 (原创内容,转载请注明来源,谢谢) 一、numpy中matrix 和 array的区别 ...

4207
来自专栏bboysoul

1167: C语言实验题――分数序列

描述:有一个分数序列:2/1, 3/2, 5/3, 8/5, 13/8, …编写程序求出这个序列的前n项之和。 输入:输入只有一个正整数n,1≤n≤10。 ...

823
来自专栏人工智能头条

十分钟掌握Keras实现RNN的seq2seq学习

1334
来自专栏林德熙的博客

C# 判断两条直线距离

d= \frac{ \left| C_1-C_2 \right|}{\sqrt{A^2+B^2}}

1022

扫码关注云+社区