The maximum profit when buying and selling a share is exactly k times
The bond value on each day is given in an array of prices
lengths n
, and I need to find the maximum profit I can make by buying and selling in exactly a k
transaction (buying and selling in this order is not the same day, but I can sell and then buy in the same day).
I tried (Python):
prices = [3, 1, 10]
n = len(prices)
def aux(i, j):
if j == n - 1 or i == 0:
return 0
s = [(prices[j + t] - prices[j]) + aux(i - 1, j + t)
for t in range(1, n - j)]
return max(aux(i, j + 1), max(s)) if s else aux(i, j + 1)
def max_profit(k):
return aux(k, 0)
But for a given array in the code and k=2
I get 9
when it should be (1 - 3) + (10 - 1) = 7
. He seems to get the maximum profit in at most k transactions, not exactly k.
How can this be fixed?
source to share
Your stop condition should not allow the function to complete successfully if k
not completely consumed. Try something like this
if i == 0:
return 0
elif j == n - 1:
return -2**30
In the first case, when i == 0
, this means that k is completely absorbed, and we can no longer act. so we can no longer win or lose, so we return 0.
Now, in the second condition, assuming that the first was not true, this means that we have reached the end of the array without complete consumption k
. Therefore, this is the wrong answer. To mark an answer as invalid, we have to give it a really bad value, so it will be rejected anyway compared to any other valid answer.
Since this is a maximization problem, bad value means a very small number, so when we maximize other answers, it will always be discarded.
-2**30
is pretty close to the minimum integer value, so it should be small enough. I am making the assumption that all your operations will match a 32-bit integer, so this should be a fairly small value. If this is not the case, you should choose a small value that should be less than the minimum value that you could get in a valid response. You can choose -2**60
or even -2**100
as it is Python and you don't have to worry about overflow issues.
source to share