Berechnen Sie alle möglichen Summen in einem Array aus seinen Sub -Arrays ⇐ Java

[Anonymous]

Ich habe ein Array von Zahlen, jetzt muss ich die Summe von Elementen finden, indem ich alle möglichen Unterarrays des angegebenen Arrays generiere und einige Bedingungen anwenden kann. Schließlich fügen Sie alle diese multiplizierten Werte für alle Subtarrays hinzu. Bereiche von
links nach rechts.

Code: Select all

Array = [2,3,2,1]
< /code>
Die Sub -Arrays sind: [start_index, end_index] < /p>
 [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

Die Antwort beträgt also 69 in diesem Fall.

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
< /code>
Dies ist der Code, den ich ausprobiert habe. < /p>
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 verringern?
Was kann ein besserer Ansatz sein, um diese Aufgabe zu lösen?

Code: Select all

David Eisenstat

hat eine großartige Antwort gegeben, aber ich finde es schwierig zu verstehen und mit einem Java -Programm zu gelangen. Kann jemand eine Java -Lösung für den Ansatz bereitstellen oder einen Pseudocode bereitstellen, damit ich ein Programm entwickeln kann.