Bei einem Integer-Array A wird der maximal mögliche Summenabstand zwischen zwei Elementen zurückgegeben. Der Summe-Abstand ist definiert als A[i] + A[j] + (i - j) für i> jMaximieren der Summenentfernung für das Integer-Array
beispielsweise mit A = [8, 2, 4, 9, 5, 8, 0, 3, 8, 2] der max Summenabstand 24 mit i = 0 und j = 8
einer O (n) erreicht wird, Lösung ist trivial. Gibt es eine O (n) Lösung (wobei n die Länge des Arrays ist)?
Dies ist möglich:
ein Array erzeugen und füllen es mit A [i] + i für jedes i
ein anderes Array erstellen und füllt sie mit einem [j] - j für jedes j
Holen Sie sich die Indizes mit der höchsten I [MAXI] und J [maxj]
Rückkehr A [MAXI] + A [Maxj] + maxi - Maxj
Dort gehen Sie, O (n)!
Könntest du den vorletzten Schritt näher ausführen? –
Keine Notwendigkeit, neue Arrays zu erstellen FWIW –
@ Niklas richtig, keine Notwendigkeit für zwei Arrays, aber es ist ein viel besser lesbarer Code, und Sie können es besser debuggen, wenn Sie einen Fehler irgendwann finden. Wenn Sie also das Maximum von 100'000'000 nicht wirklich berechnen müssen, müssen Sie keine Mikrooptimierungen durchführen, die Ihren Code durcheinander bringen. – xXliolauXx
Für jeden Index i müssen wir nur einen index kennen, der die Summe A[i] + A[index] + (i - index) = A[i] + i + (A[index] - index) maximiert. Was bedeutet, wir müssen nur eine index pflegen, die A[index] - index ist maximal.
int index = 0;
int result = 0;
for(int i = 1; i < n; i++){
int total = A[i] + i + A[index] - index;
result = max(result, total);
if(A[i] - i > A[index] - index){
index = i;
}
}
return result;
Nette Lösung, weniger Code, aber etwas unordentlicher als meiner Meinung nach ... – xXliolauXx
Sie können nicht ernsthaft eine Lösung in Betracht ziehen, die zwei riesige Arrays besser speichert als eine Lösung, die eine ganze Zahl verfolgt. – Stef
@Stef Es hängt von der Verwendung ab. Was auch immer, sie sind im Grunde der gleiche Ansatz, ein nützlicher für riesige Arrays in der Größenordnung von 10^6, der andere besser debugbar. Da er nicht erwähnte, dass er massive Arrays durchgehen musste, schrieb ich die debugable Version. – xXliolauXx
wunderbare lös ... Pham ... danke. lesbare ige Lösung könnte sein ...
int sumP = Integer.MIN_VALUE;
int sumQ = Integer.MIN_VALUE;
for(int i = 0; i < A.length; i++){
sumP = Math.max(A[i] - i, sumP);
sumQ = Math.max(A[i] + i, sumQ);
}
return sumP + sumQ;
Excellent antwort kannst du bitte ausarbeiten? –
// Das war die genaueste Lösungsmethode, die den Test bei 100% bestanden .`
var sumP = MIN_VALUE*2;
var sumQ = MIN_VALUE*2;
for(var i = 0; i < A.length; i++){
sumP = Math.max(A[i] - i, sumP);
sumQ = Math.max(A[i] + i, sumQ);
}
return sumP + sumQ;
Sicher, als 'max (A [i] + i für i im Bereich (len (A)) + max (A [j] - j für j im Bereich (len (A))). Dann sehe ich, wie du den Absolutwert oder die Einschränkung "i" bearbeitest j, und dann suche ich nach dem Duplikat –
@DavidEisenstat Macht das überhaupt einen Unterschied? Es scheint, als ob i - j negativ ist, gibt es eine bessere Lösung mit i und j ausgetauscht. In diesem Fall denke ich, können wir noch Markieren Sie es als Duplikat, wenn Sie nicht zu viel Mühe haben, es zu finden –
@NiklasB. Nun, wurde vorher gefragt, aber nicht beantwortet: http://stackoverflow.com/questions/31139032/in-an-array-find-the-largest-sum-distance-between-any-2-elements. Will dupe schließen Sie das hier hinein. –