Efficiently generate list of lightest intervals of a vector
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.