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 -> 0
1:0 : 0
2:1 : 4 0 > 0 1
3:5 : 4 0 1 = 0 1 4 BUT: 1 1 1 would be cheaper
4:6 : 1 4 0 1 < 4 0 1 4
5:7 : 1 1 4 0 1 < 1 4 0 1 4
6:8 : 1 1 1 4 0 1 < 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 < 3 0 0 1 1
4:3: 0 3 0 0 < 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 < 3
Is it possible to find the interval weights in time $o(n^2)$? Is it possible to approximate them with lower runtime?