Open-and-close-interval DP doubt

Revision en2, by venti, 2021-04-18 10:20:28

Reading through this DP blogpost by zscoder

In the "open and close interval" section, the blogpost explains this problem —

The explanation says -

"Suppose there are j open sets. When we add a[i], the sum a[i] - a[i - 1] will contribute to each of the j open sets, so we increase the current imbalance by j(a[i] - a[i - 1])."

But doesn't this imply that all j open sets contain a[i-1]?

Shouldn't the correct net increase in imbalance be - sum(a[i] - max(cur_open_set)) // (assuming we somehow tracked the max for each cur_open_set)

But for my equation to be equal to j*(a[i]-a[i-1]), all the current open sets would need to have a[i-1] in them. So how does this work?

Basically I'm unable to understand the transition of the 3rd state in the DP equation in the blogpost. If anyone can help clarify my misunderstanding or explain it in a different way, I'd be grateful!

Please help! Thanks!


  Rev. Lang. By When Δ Comment
en2 English venti 2021-04-18 10:20:28 300 (published)
en1 English venti 2021-04-18 10:11:31 1158 Initial revision (saved to drafts)