Given an array arr = [9 8 2 4 6 3 5 1 7]

The goal is to maximize saving.

Partition the wall anywhere on a given day. You get to keep the side with the smaller amount, and the bigger side gets eaten up by animals.

For ex: arr = [9 8 2 4 | 6 3 5 1 7]
=> Left - 23 and right - 22, so animals will take the left side and you get 22 on day 1.

Then you put another partition on the side (subarray) that was left. Ex: arr = [6 3 | 5 1 7]

You get to keep the smaller side. So the total amount saved so far is the amount saved on day 1 + day 2 => 22 + 9 = 31.

Keep doing this until everything is eaten by the animals.

Goal is to find the maximum amount that you can save combined.

Meaning the partition doesn't have to be where the difference is the smallest.

Thought process:

Split at index k
, then findMax(arr[0...n]) = min(sum(arr[0...k]) + findMax(arr[0...k]), sum(arr[k...n]) + findMax(arr[k...n]))

How can this be done in O(n2) ?

Thanks