Efficiently generate list of lightest intervals of a vector Suppose a vector of size $n$ is given. The goal is to compute, $\forall i \in [n]$ the lightest interval of size $i$ (i.e. the interval whose sum is minimal).

For example, if we have the array:

1 1 0 0 1 2 1 0 0 0 1


For any length n, the minimal weight of $i$ length interval is:

interval size:              1  2  3  4  5  6  7  8  9  10 11
interval weight:            0  0  0  1  2  4  4  4  5  6  7


A naive algorithm would compute the shortest interval for each $i$ by itself, which results in a $O(n^2)$ time algorithm (keeping a sliding window of size $i$).

If we attempt a greedy "triangle" algorithm (start from the smallest number, expand by 1 each time), it fails, no matter if we try it botom-up or top-down:

A triangle algorithm would fail at 1 1 1 4 0 1 4

1 1 1 4 0 1 4 -&gt; 0
1:0 :         0
2:1 :       4 0 &gt; 0 1
3:5 :       4 0 1 = 0 1 4     BUT: 1 1 1 would be cheaper
4:6 :     1 4 0 1 &lt; 4 0 1 4
5:7 :   1 1 4 0 1 &lt; 1 4 0 1 4
6:8 : 1 1 1 4 0 1 &lt; 1 1 4 0 1 4
7:12: 1 1 1 4 0 1 4


A reverse triangle algorithm would fail at 0 3 0 0 1 1

6:5: 0 3 0 0 1 1
5:4: 0 3 0 0 1 &lt; 3 0 0 1 1
4:3: 0 3 0 0 &lt; 3 0 0 1     BUT: 0 0 1 1 would be cheaper!
3:3: 0 3 0 == 3 0 0        BUT: 0 0 1 would be cheaper!
2:3: 0 3 == 3 0            BUT: 0 0 would be cheaper!
1:0: 0 &lt; 3


Is it possible to find the interval weights in time $o(n^2)$? Is it possible to approximate them with lower runtime?
You can build the whole table using the following $O(n^2)$ construction:

1: 1   1   0 z:0 w:1   2   1   0   0   0   1    
2:   2   1   0   1   3   3   1   0   0   1
3:   y:2   1   1   3   4 v:3   1   0   1
4:     x:2   2   3   4 u:4 ...
5:        ...
...


At every step you are calculating the value $x$ at the top of a "reversed triangle", and the value is simply the sum of an adjacent element in the previous row ($y$ in the figure) and the opposite vertex at the base of the triangle ($z$ in the figure).

*         z
 ...   ...
   y   *
     x
x = y + z


or equivalently:

w         *
 ...   ...
   *   v
     u
u = v + w


For each row the difficulty is given by the lower element of that row.