Will be video-editorials that you've made live on Hopin be published anywhere, or they were not saved?

Thank you

How to prove this "most important observation"? I tried for an hour but couldn't quite get it right. It relies also on the fact that all numbers are >= 0, right?

I think I finally came up with a proof that works after trying for many hours :) misof Is this the proof you had in mind?

Definitions

Valid segmentation of length $$$i :=$$$ a way to cut up the array into $$$i$$$ contiguous segments (using $$$i - 1$$$ cuts) such that the sum of values in each segment is $$$<=$$$ sum of values in next segment.

$$$M_l :=$$$ minimum width among any valid segmentation of length $$$l$$$

$$$[i:j] :=$$$ contiguous subarray starting at index $$$i$$$ and ending at index $$$j$$$

Theorem

f there exists a valid segmentation of length $$$k$$$ in an array where all values $$$>= 0$$$, then $$$M_k <= M_{k - 1}$$$, for any $$$k >= 2$$$.

In words: When cutting the array up into more segments the minimum possible width only goes down.

Proof (by induction)

Inductive hypothesis

If there exists a valid segmentation of length $$$k$$$ ($$$k >= 2$$$) in an array with values $$$>= 0$$$, then $$$M_k <= M_{k - 1}$$$.

Base case

It holds for $$$k = 2$$$ since the only valid segmentation of length 1 has width $$$N$$$ (where $$$N$$$ is the length of the array), and any valid segmentation of length 2 has width $$$< N$$$.

Inductive step

Assume it holds for $$$k - 1$$$. Now we must prove that it holds for length $$$k$$$. If there does not exist a valid segmentation of length $$$k$$$, then the conditional statement in the theorem does not hold and the proof holds. Therefore we can assume for the remainder of the proof that a valid segmentation of length $$$k$$$ exists.

Let's assume by contradiction that the inductive step does not hold and that instead $$$M_{k - 1} < M_k$$$. This scenario is depicted in the drawing below (array ends at index $$$i$$$).

k segments
xx | xx | xx | xx | xxxxx 
                ^   <--->
                |    M_k     
                |
        index i - M_k

k - 1 segments
xx | xxx | xxxx | xxxx 
              ^   <-->
              |   M_{k-1}       
              |
      index i - M_{k-1}

From the definition of $$$M_{k}$$$, we know that it is possible to split prefix $$$[0:i-M_k]$$$ (see drawing) into $$$k - 1$$$ segments. From the contradiction hypothesis we also have that $$$i - M_{k - 1} > i - M_k$$$, and therefore it is possible to split $$$[0:i-M_{k - 1}]$$$ into $$$k - 2$$$ segments.

From the inductive hypothesis we know that $$$M_{k - 1} <= M_{k - 2}$$$. Therefore instead of cutting $$$[0:i-M_{k - 1}]$$$ into $$$k - 2$$$ segments, we can cut it into $$$k - 1$$$ segments and achieve a width that is not greater than it. Then we add on top of it segment $$$[i-M_{k-1}+1:i]$$$ which is guaranteed to make a valid segmentation since the width of the $$$k-1$$$'th segment is not greater than before. Note: this argument only holds because all values in array are $$$>= 0$$$.

We have now achieved a valid segmentation of $$$k$$$ segments with a width of $$$M_{k - 1} < M_{k}$$$. This is a contradiction (since we defined $$$M_{k}$$$ to be the minimum width among any valid segmentation of length $$$k$$$), and therefore our hypothesis was wrong. Therefore we must have $$$M_{k - 1} >= M_{k}$$$ which proves the inductive step.

Corollary

Let's choose in the theorem above $$$k$$$ to be equal to be the maximum valid segmentation. Then we have that $$$M_k <= M_{k - 1} <= ... <= M_{2}$$$. Therefore there exists a maximum segmentation whose width is equal to the minimum width among any valid segmentation.