Subarray minimalnej sumy w O (N) według algorytmu Kadane'a

Question

Wszyscy wiemy o podsumowie sumy maksymalnej i słynnym Kadane's algorithm. Ale czy możemy użyć tego samego algorytmu, aby znaleźć również minimalną sumę?

My się to:

zmienić znak i znaleźć maksymalną sumę na tym, że sam jako sposób obliczyć maksymalną subarray sumy. Następnie zmień znak elementów w tablicy, aby był początkowy.

Proszę mi pomóc w poprawieniu algo, jeśli ma jakiekolwiek problemy.

przypadek rogu: wiem, że jest to kwestia, czy wszystkie elementy są pozytywne i możemy obsługiwać tę sprawę, wykonując pewne wstępne przetwarzanie tj poligonowego tablicy jeśli wszystkie są ve nie tylko zwróci minimalną liczbę z tablicy.

Powyższy algorytm zadziała i będzie obsługiwany (wyjaśniony) przez dasblinkenlight.

Answer 1

Czy podejście, o którym wspomniałem, pozwoli znaleźć minimalną kwotę?

Tak, będzie. Możesz ponownie zgłosić problem znalezienia minimalnej sumy jako znalezienie ujemnej sumy o największej bezwzględnej wartości. Kiedy zmienisz znaki swoich liczb i zachowasz resztę algorytmu na miejscu, jest to liczba, którą algorytm wróci do ciebie.

wiem, że jest to kwestia, czy wszystkie elementy są pozytywne

Nie, nie ma problemu: algorytm rozważyć oryginalnej Kadaně, gdy wszystkie elementy są negatywne. W tym przypadku algorytm zwraca pustą sekwencję dla sumy zerowej - najwyższą możliwą w danych warunkach. Innymi słowy, gdy wszystkie elementy są ujemne, najlepszym wyjściem jest nie brać żadnego z nich.

Twój zmodyfikowany algorytm zrobi to samo w przypadku, gdy wszystkie liczby będą dodatnie: znowu, najlepszym rozwiązaniem jest nie przyjmowanie liczb w ogóle.

Jeśli dodasz wymaganie, że zakres powracający z algorytmu może nie być pusty, możesz zmodyfikować algorytm nieznacznie, aby znaleźć najmniejszą dodatnią liczbę (lub największą liczbę ujemną) w przypadku, gdy algorytm Kadane zwróci pusty zakres jako optymalne rozwiązanie.

Answer 2

Po prostu zamień max na min.

//O(n) 
public static int minSubArraySum(int[] arr) { 
    int minSum = 0; 
    int curSum = 0; 
    for (int i : arr) { 
     curSum += i; 
     minSum = Math.min(minSum, curSum); 
     curSum = Math.min(curSum, 0); 
    } 
    return minSum; 
}