Ich wurde heute im Adobe-Interview für die Position des Softwareentwicklers folgende Frage gestellt:
Problem Gegeben ein Array arr[1..n] von ganzen Zahlen. Schreiben Sie einen Algorithmus, um die Summe des zusammenhängenden Subarrays innerhalb des Arrays mit der größten Summe zu finden. Geben Sie 0 zurück, wenn alle Zahlen negativ sind.
Beispiel
Gegebenes Array arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]
Antwort
83 erstellt mit [ 12, 14, 0, -4, 61 ] .
Ich könnte mir eine Lösung in O(n logn) vorstellen, aber ich glaube nicht, dass sie sehr effizient ist. Der Interviewer hat mich gebeten, einen O(n) -Algorithmus zu schreiben. Ich konnte nicht darauf kommen.
Irgendeine Idee, wie man eine O(n) Lösung für dieses Problem schreibt?
Algorithmus, der entweder in C / C ++ / Java implementiert wird.
Vielen Dank im Voraus
Sie können den Kadane-Algorithmus verwenden, der in O (n) läuft.
Hier ist der Algorithmus (schamlos kopiert von hier )
%Vor%