I don’t understand the correctness proof of the book’s algorithm.
Especially for the sentence “Therefore, a must be assigned to a* at some iteration. At this point, b <= b* since A[a* - 1, b - 1] satisfies the sum constraint”.
How can we guarantee A[a* - 1, b - 1] <= k? And where does A[a* - 1, b - 1] come from?
Can anyone elaborate the proof in more details?
Thanks in advance.