Zählung der Anzahl der Summen aus benachbarten Unterfeldern eines Feldes

Wir erhalten ein Array mit allen a [ i ] > 0 .$a[1 \ldots n]$$a[i]>0$

Nun müssen wir herausfinden, wie viele verschiedene Summen aus ihren Subarrays gebildet werden können (wobei ein Subarray ein zusammenhängender Bereich des Arrays ist, dh für einige j , k , die Summe ist die Summe aller Elemente des Subarrays). Wenn beispielsweise a = [ 1 , 2 , 1 ] ist , lautet die Antwort 4: Wir können 1 , 2 , 3 , 4 bilden .$a[j\ldots k]$$j,k$$a=[1,2,1]$$1,2,3,4$

Ich weiß, wie man die Anzahl verschiedener Summen in .$O(n^2)$

Darüber hinaus wurde mir klar, dass dies dem klassischen Problem ähnelt, bei dem die Anzahl der unterschiedlichen Teilzeichenfolgen einer Zeichenfolge ermittelt werden muss. Ich dachte über die Möglichkeit nach, ein Suffix-Array zu konstruieren und auf ähnliche Weise zu lösen (in -Zeit). Aber ich habe nicht herausgefunden, wie ich das ändern kann, damit es hier funktioniert. Wenn wir beispielsweise das Suffix-Array für a = [ 1 , 2 , 1 ] verwenden, erhalten wir 5 Fälle anstelle der vier zulässigen Fälle. Ist dies mit Suffix-Arrays möglich oder denke ich in die falsche Richtung?$O(n)$$a=[1,2,1]$

$O(m)$

$O(n^2)$$\Theta(n^2)$

$[1,2,4,8,\dotsc, 2^n]$$\frac{n(n+1)}2$

Das "fast sicher" liegt daran, dass das Problem die Werte der Summen nicht als Ausgabe benötigt. Ich glaube jedoch nicht, dass Duplikate vermieden werden können, ohne zumindest die meisten Werte zu bestimmen.