kittyK's blog

By kittyK, history, 4 years ago, In English

In this UVA 10755 — Garbage Heap , we have to find maximum sum of any sub range.

I have seen the solution and editorial available online . But I don't understand the insight . How 2d max sum and kadane algorithm is applying to get the ans. I meant How it is working actually .

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hello,

I haven't looked at the solution, but here's how I would do it. The rectangular prism you end up choosing will be bounded to the left and right, on the top and bottom, and in the front and back. Call these bounds $$$x_1$$$ and $$$x_2$$$, $$$y_1$$$ and $$$y_2$$$, and $$$z_1$$$ and $$$z_2$$$, respectively. Now, what we can do is consider all possibilities of $$$x_1$$$, $$$x_2$$$, $$$y_1$$$, and $$$y_2$$$. This is akin to checking all possible shadows of the prism in the $$$xy$$$-plane.

Now how do we efficiently find the maximum prism with any given shadow? Consider the $$$xy$$$ cross sections of the prism: the rectangles of garbage pieces that lie within the shadow at any given $$$z$$$ value. There are up to $$$C$$$ of these cross sections, and the prism will end up consisting of any contiguous series of these cross sections. First, we use 2D sums to calculate the sum of each of these cross sections (note that we're going to use a separate 2D sum array for each $$$z$$$ value). Now this is where Kadane's algorithm steps in: we want the maximum sum of any subarray of these cross-section sums. This value will be the maximum sum of any rectangular prism with the given shadow. Note that we can do all of this in $$$O(C)$$$ because there are $$$C$$$ cross sections.

Putting it all together, we first check all possible values of $$$x_1$$$, $$$x_2$$$, $$$y_1$$$, and $$$y_2$$$. Then for each possible configuration of these values we do an $$$O(C)$$$ check for the most valuable prism with that shadow. In total, there are $$${A \choose 2}{B \choose 2}$$$ shadows, which is $$$O(A^2B^2)$$$. This means we have an overall $$$O(A^2B^2C)$$$ solution.