The cost of a bond on each day is given in array prices of length n, and I need to find the maximum profit that I can make by buying and selling in exactly k transactions (buying and selling, in that order. not in 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 the given array in the code, and with k=2 I get 9 when It should be (1 - 3) + (10 - 1) = 7. It seem to get the maximum profit for at most k transactions and not exactly k. How can it be fixed? Continue reading...
