25.3 need more thorough explanation

#1

Trying to wrap my head around the solution for 25.3 and not understanding how the first algorithm is O(kn^2) and actually not understanding what this first algorithm is supposed to do. Is it iterating i := 0 through A.size() and at each i, calculate j pairs? Or does it just calculate j pairs once from 0 through A.size()?

Also, it would be great to include some examples and a more thorough explanation of the optimal solution. Totally not understanding it.

Thanks,

tacocat

0 Likes
#2

Hey @tacocat,

Use some concrete example will be easier to think here. It is like we assume k = 1 (even k might be greater than), we just run the original algorithm for each A[0:i], and then store that in an array. Then you progress to the next k value, and so on so forth. With that, you can get an O(kn^2) algorithm.

About the optimal algorithm, we are trying to rewrite as it is definitely hard to understand due to the difficulty of this problem.

Please let us know if you have any other problem.

0 Likes
#3

This video helped me understand the solution, though I think from the comments the jth transaction expression should be “price[j] - price[m] + T[i - 1][m - 1]” since you cannot buy and sell a stock on the same day. It’s basically dynamic programming

0 Likes