Berechnen Sie alle möglichen Summen in einem Array aus seinen Unterarrays
Posted: 28 Dec 2024, 17:52
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:
Die Unterarrays sind: [start_index, end_index]
In diesem Fall lautet die Antwort also 69.
Einschränkungen:
Das ist der Code, den ich ausprobiert habe.
Ich möchte die zeitliche Komplexität dieses Algorithmus reduzieren?
Was könnte ein besserer Ansatz zur Lösung dieser Aufgabe sein?
Update: 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>
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]
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
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
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;
}
Was könnte ein besserer Ansatz zur Lösung dieser Aufgabe sein?
Update:
Code: Select all
David Eisenstat