最佳买卖股票的修改版本 [英] Best time to Buy and Sell stock modified version

问题描述

假设您有一个数组，第i个元素是第i天给定股票的价格.

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

如果您可以进行无限次的买卖(一次只能持有一只股票)，但是每次出售都需要支付交易费，请计算您可以获取的最大利润.

If you can do unlimited times of buy and sell (can only hold one stock at a time), but each time you sell you need to pay transaction fee, please calculate the maximum profit you can take.

示例输入{1，3，7，5，10，3}费用= 3.

Sample input { 1, 3, 7, 5, 10, 3 } fee = 3.

如果您进行两次交易，则总利润为(7-1)-3 +(10-5)-3 = 5. 如果仅进行一项交易，则总利润为(10-1)-3 = 6.

If you do two transactions, the total profit is (7 - 1) - 3 + (10 - 5) - 3 = 5. If you only to one transaction, the total profit is (10 - 1) - 3 = 6.

public int maxProfit(int[] prices, int fee) {}

原始版本非常简单，但是我不确定如何处理此修改版本.谁能给我一些提示/指导?我正在研究面试的算法问题.

The original version is pretty straightforward but I'm not sure how to approach this modified version. Can anyone give me some hints/guidance? I'm studying algorithm problems for interviews.

推荐答案

可以通过应用动态编程技术来解决此问题.

This problem can be solved by applying Dynamic programming technique.

让我们为这个问题建立一个递归公式.

Let's form a recursive formula for this problem.

从第一天开始，我们将迭代到最后一天.每天有两种情况需要我们做出决定:

Starting from the first day, we will iterate through the last day. For each day, there are two cases which we will need to make decision:

• 要么我们手中只有一只股票，我们需要决定是否将其持有至第二天，或者我们卖掉它并获得一些利润
• 或者我们没有任何库存，我们需要决定是购买还是要等到第二天.

所以，这是公式，假设我们现在是current_day

So, here is the formula, let's say we are at day current_day

int result = 0;
if have_stock{
    result = max(prices[current_day] - fee + f(current_day + 1, no_stock), f(current_day + 1, have_stock));
}else{
    result = max(-price[current_day] + f(current_day + 1, have_stock) , f(current_day + 1, no_stock));
}

现在，我们看到，可以通过使用两个变量current_day和have_stock =>来表示问题，我们可以使用简单的dp[n][2]表来存储结果.时间复杂度将为O(n)

Now, we see that, the problem can be represented by using two variables, current_day and have_stock => we can use a simple dp[n][2] table to store the result. Time complexity will be O(n)

这篇关于最佳买卖股票的修改版本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！