Berechnen Sie alle möglichen Summen in einem Array aus seinen Unterarrays ⇐ Java

[Guest]

Ich habe ein Array von Zahlen, jetzt muss ich die Summe der Elemente ermitteln, indem ich alle möglichen Unterarrays des gegebenen Arrays erzeuge und einige Bedingungen anwende.
Die Bedingung gilt für jedes Unterarray Holen Sie sich das Minimum und ermitteln Sie auch die Gesamtzahl der darin enthaltenen Elemente und multiplizieren Sie beide (Minimum * Gesamtsumme). Fügen Sie abschließend alle diese multiplizierten Werte für alle Unterarrays hinzu.
Hier ist die Problemstellung:
Ermitteln Sie die Summe aller möglichen Unterarrays mithilfe der folgenden Formel:

Sum(left, right) = (min of arr) * (∑ arr), wobei i von
left bis reicht richtig.

Beispiel:

Code: Select all

Array = [2,3,2,1]

Die Unterarrays sind: [start_index, end_index]

Code: Select all

 [0,0] subarray = [2], min is 2 and total of items = 2. min * total = 2*2=4
[0,1] subarray = [2,3], min is 2 and total of items = 5. min * total = 2*5=10
[0,2] subarray = [2,3,2], min is 2 and total of items = 7. min * total = 2*7=14
[0,3] subarray = [2,3,2,1], min is 1 and total of items = 8. min * total = 1*8=8

[1,1] subarray = [3], min is 3 and total of items = 3. min * total = 3*3 = 9
[1,2] subarray = [3,2], min is 2 and total of items = 5. min * total = 2*5 = 10
[1,3] subarray = [3,2,1], min is 1 and total of items = 6. min * total = 1*6 = 6

[2,2] subarray = [2], min is 2 and total of items = 2. min * total = 2*2 = 4
[2,3] subarray = [2,1], min is 1 and total of items = 3. min * total = 1*3 = 3

[3,3] subarray = [1], min is 1 and total of items = 1. min * total = 1*1 = 1

Total = 4 + 10 + 14 + 8 + 9 + 10+ 6 + 4 + 3 + 1 = 69

In diesem Fall lautet die Antwort also 69.
Einschränkungen:

Code: Select all

Each array element is in range 1 to 10^9. Array size 1 to 10^5. Return response in modulo 10^9+7

Das ist der Code, den ich ausprobiert habe.

Code: Select all

public static int process(List list) {
int n = list.size();
int mod = 7 + 1000_000_000;
long result = 0;
for (int i = 0; i < n; i++) {
long total = 0;
int min = list.get(i);
for (int j = i; j < n; j++) {
int p = list.get(j);
total = (total + p) % mod;
min = Math.min(min, p);
result = (result + (min * total) % mod) % mod;
}
}
return (int) result;
}

Ich möchte die zeitliche Komplexität dieses Algorithmus reduzieren?
Was könnte ein besserer Ansatz zur Lösung dieser Aufgabe sein?
Update:

Code: Select all

David Eisenstat

hat eine tolle Antwort gegeben, aber ich finde es zu schwierig, ein Java-Programm zu verstehen und zu erstellen. Kann jemand eine Java-Lösung für diesen Ansatz oder einen Pseudocode bereitstellen, damit ich ein Programm erstellen kann? P>