24.38 Find the longest subarray whose sum <= k

#1

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.

2 Likes

#2

Have the same question!

0 Likes

#3

“Therefore, a must be assigned to a* at some iteration."
That means a* - 1 will move to a* at some iteration for certain.

A[a* - 1, b - 1] has the a* parameter as a constant. It is the optimal left boundary. But b is still a variable.

“At this point, b <= b* since A[a* - 1, b - 1] satisfies the sum constraint” can be framed as
“If A[a* - 1, b - 1] satisfies the sum constraint, b <= b*.”
So, for some b, A[a* - 1, b - 1] <= k. In that case, b <= b*. The latter now has to be proven.

This way, these endpoints act as candidates to be considered for optimality. Then, you can compare (b - 1) - (a* - 1) + 1 = b - a* + 1 with b* - a* + 1.
b vs b* are the only terms to consider for the comparison then.

Please let me know if there is any flaw in the reasoning.

0 Likes