Finden Sie die maximale Intervall Summe in einer Liste der reellen zahlen

Es ist O(N):

int sum = 0;
int M = 0;  //This is the output
foreach (int n in input)  {
  sum += n;
  if (sum > M)
      M = sum;

  if (sum < 0)
    sum = 0;
}

Der Idee zu halten, ist die Summe aller ganzen zahlen, die aufgetreten sind seit dem letzten zurücksetzen. Eine Rückstellung erfolgt, wenn die Summe geht unter null, d.h. es gibt zu viele negative zahlen im aktuellen Intervall zu machen, vielleicht die beste.

Versuchen, diesen code .. es würde funktionieren für mindestens eine +ve-Zahl im array.. O(n) nur eine for-Schleife verwendet..

public static void main(String[] args) {
    int length ;
    int a[]={ -12, 14, 0, -4, 61, -39};  
    length=a.length;

    int absoluteMax=0, localMax=0, startIndex=0, lastIndex=0, tempStartIndex=0;
    for (int index=0;index<length;index++) {
        localMax= localMax + a[index];
        if(localMax < 0){ localMax=0; tempStartIndex = index + 1;}
        if(absoluteMax < localMax) {
            absoluteMax = localMax; 
            lastIndex =index; 
            startIndex=tempStartIndex;
        }
    }

    System.out.println("startIndex  "+startIndex+"  lastIndex "+ lastIndex);    
    while (startIndex <= lastIndex) {
        System.out.print(" "+a[startIndex++]);
    }
}

Ich bin dringen auf diesen alten thread, um eine detaillierte Erklärung, warum der Kadane-Algorithmus funktioniert. Der Algorithmus wurde vorgestellt in einer Klasse, die ich derzeit nehmen, aber nur eine vage Erklärung. Hier ist eine Implementierung des Algorithmus in Haskell:

maxCont l = maxCont' 0 0 l

maxCont' maxSum _ [] = maxSum
maxCont' maxSum thisSum (x:xs)
  | newSum > maxSum = maxCont' newSum newSum xs
  | newSum < 0      = maxCont' maxSum 0 xs
  | otherwise       = maxCont' maxSum newsum xs
  where
    newSum = thisSum + x

Nun, da wir versuchen nur zu verstehen, der Algorithmus, lassen Sie ' s rückgängig machen, die kleine Optimierung der Namensgebung newSum:

maxCont l = maxCont' 0 0 l

maxCont' maxSum _ [] = maxSum
maxCont' maxSum thisSum (x:xs)
  | thisSum + x > maxSum = maxCont' (thisSum + x) (thisSum+x) xs
  | thisSum + x < 0      = maxCont' maxSum 0 xs
  | otherwise            = maxCont' maxSum (thisSum+x) xs

Was ist diese verrückte Funktion maxCont'? Wir kommen mit einer einfachen Angabe, was es tun soll. Wir wollen die folgende zu halten, mit der Voraussetzung, dass 0 ≤ thisSum ≤ maxSum:

maxCont' maxSum thisSum [] = maxSum
maxCont' maxSum thisSum l  = maximum [maxSum, thisSum + maxInit l, maxCont l]

wo maxInit l ist die größte Summe aus einem ersten segment von l und maxCont ist die maximale zusammenhängende Summe von l.

Triviale, aber wichtige Tatsache: für alle l, maxInit l ≤ maxCont l. Es sollte offensichtlich sein, dass die oben genannte Spezifikation garantiert maxCont l = maxCont' 0 0 l werden, was wir wollen. Anstatt zu versuchen, zu erklären, direkt, warum die Finale version von maxCont' implementiert die Spezifikation oben (die ich nicht wirklich wissen, wie zu tun), werde ich zeigen, wie es kann daraus abgeleitet werden, die Umwandlung der Spezifikation einen Schritt zu einer Zeit, bis es wird der code, der wird dann sicherlich richtig sein. Wie geschrieben, ist diese Angabe nicht geben-Implementierung: wenn maxCont ist definiert in Bezug auf maxCont' wie oben beschrieben, wird die Schleife für immer als maxCont' Anrufe maxCont Anrufe maxCont' mit der gleichen Liste. Also lassen Sie es erweitern sich nur ein bit zu setzen die Stücke, die wir benötigen:

maxCont' maxSum thisSum (x:xs) =
                     maximum [maxSum, thisSum + maxInit (x:xs), maxCont (x:xs)]

Diese nicht alles reparieren, aber es ausgesetzt Dinge. Lasst uns das nutzen. thisSum + maxInit (x:xs) ist entweder thisSum oder thisSum + x + maxInit xs. Aber thisSum ≤ maxSum mit der Voraussetzung, so können wir ignorieren diese Möglichkeit bei der Berechnung der maximalen. maxCont (x:xs) ist eine Summe, die entweder x oder nicht. Aber wenn es auch x, dann ist es das gleiche wie maxInit (x:xs) unter der vorhergehenden, so können wir ignorieren diese Möglichkeit, nur den Fall betrachten, wo maxCont (x:xs) = maxCont xs. So kommen wir zu der nächsten version:

maxCont' maxSum thisSum (x:xs) = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]

Diese, schließlich, ist richtig, rekursiver, aber wir haben Möglichkeiten, um zu gehen, um zu effizienten code, vor allem, weil das mythische maxInit zu langsam wäre. Lassen Sie uns es brechen in den drei Fällen, als in den Java-code (Missbrauch von Haskell-notation ein bisschen):

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
  | thisSum + x < 0          = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
  | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]

Im ersten Fall wissen wir, dass maxSum können nicht das maximum: thisSum+x ist größer und maxInit xs ist immer positiv. Im zweiten Fall wissen wir, dass thisSum+x+maxInit xs können nicht das maximum: maxCont xs ist immer mindestens so groß wie maxInit xs, und thisSum+x negativ ist. So können wir vermeiden diesen Möglichkeiten:

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maximum [        thisSum+x+maxInit xs, maxCont xs]
  | thisSum + x < 0          = maximum [maxSum,                       maxCont xs]
  | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]

Nun haben wir gerade genug von einer Kante zu drehen die Dinge um. Jetzt haben wir beseitigt Fällen unmöglich, wir fügen Sie einige doppelte Fällen, die diese drei Fälle wieder in der gleichen form, so können wir Ersatz in der ursprünglichen Spezifikation von maxCont'. Im ersten Fall, wir haben nicht einen ersten Begriff, also brauchen wir etwas, das wir kennen, wird nicht mehr als die anderen Bedingungen. Zur Aufrechterhaltung der invariante, dass thisSum ≤ maxSum wir brauchen, um den thisSum+x. Im zweiten Fall haben wir nicht einen zweiten Begriff, der aussieht wie something+maxInit xs, aber wir wissen, dass maxInit xs ≤ maxCont xs, so können wir sicher stick in 0+maxInit xs. Das hinzufügen dieser extra Bedingungen für die Regelmäßigkeit der Erträge die folgenden:

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maximum [(thisSum+x), (thisSum+x)+maxInit xs, maxCont xs]
  | thisSum + x < 0          = maximum [maxSum,      0+maxInit xs,           maxCont xs]
  | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum,      thisSum+x+maxInit xs,   maxCont xs]

Schließlich, nach der überprüfung der Voraussetzung, ersetzen wir in der Spezifikation,

maxCont' maxSum thisSum l = maximum [maxSum, thisSum + maxInit l, maxCont l]

bekommen

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maxCont' (thisSum+x) (thisSum+x) xs
  | thisSum + x < 0          = maxCont' maxSum 0 xs
  | 0 ≤ thisSum + x ≤ maxSum = maxCont' maxSum (thisSum+x) xs

Fixieren diese in real-syntax und fügen die base weggelassen Fall ergibt sich der tatsächliche Algorithmus, das haben wir jetzt bewiesen, erfüllt die spec so lange, wie es endet. Aber jeder der aufeinander folgenden rekursiven Schritt arbeitet auf eine kürzere Liste, so tut es in der Tat kündigen.

Es gibt nur eine Letzte Sache zu tun, für meinen Willen, die zu schreiben, die letzten code mehr idiomatically und flexibel:

maxCont :: (Num a, Ord a) => [a] -> a
maxCont = fst . foldl maxCont' (0,0)
  where
    maxCont' (maxSum, thisSum) x
      | maxSum < newSum = (newSum, newSum)
      | newSum < 0      = (maxSum, 0)
      | otherwise       = (maxSum, newSum)
      where newSum = thisSum + x

Ich würde eine Antwort, die enthält 2 Ansätze, das handle-array mit oder ohne positiven Elementen, geschrieben in Java.

Code - Java

MaxSubSum.java:

public class MaxSubSum {
    /**
     * Find max sub array, only include sub array with positive sum.
     * <p>For array that only contains non-positive elements, will choose empty sub array start from 0.
     * <p>For empty input array, will choose empty sub array start from 0.
     *
     * @param arr input array,
     * @return array of length 3, with elements as: {maxSum, startIdx, len};
     * <p>tips: should use 'len' when loop the returned max sub array, so that it could also work for empty sub array,
     */
    public static int[] find(int[] arr) {
        if (arr.length == 0) return new int[]{0, 0, 0}; //empty array, no sub array,

        int maxSum = 0;    //max sum, found so far,
        int maxStart = 0;  //start of max sum,
        int maxLen = 0;    //length of max subarray,

        int sum = 0;  //current sum,
        int start = 0;    //current start,

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0) { //get a positive,
                if (sum <= 0) {  //should restart,
                    start = i;
                    sum = arr[i];
                } else sum += arr[i];

                if (sum > maxSum) { //get a larger sum,
                    maxSum = sum;
                    maxStart = start;
                    maxLen = i - start + 1;
                }
            } else sum += arr[i]; //0 or negative number,
        }

        return new int[]{maxSum, maxStart, maxLen};
    }

    /**
     * Find max sub array, also include sub array with non-positive sum.
     * <p>For array that only contains non-positive elements, will choose first smallest element.
     * <p>For empty input array, will choose empty sub array start from 0.
     *
     * @param arr input array,
     * @return array of length 3, with elements as: {maxSum, startIdx, len};
     * <p>tips: should use 'len' when loop the returned max sub array, so that it could also work for empty sub array,
     */
    public static int[] findIncludeNonPositive(int[] arr) {
        if (arr.length == 0) return new int[]{0, 0, 0}; //empty array, no sub array,

        int maxSum = arr[0];    //max sum, found so far,
        int maxStart = 0;    //start of max sum,
        int maxLen = 1;    //length of max subarray,

        int sum = arr[0];  //current sum,
        int start = 0;    //current start,

        for (int i = 1; i < arr.length; i++) {
            if (sum <= 0) { //should restart,
                start = i;
                sum = arr[i];
            } else sum += arr[i];

            if (sum > maxSum) { //get a larger sum,
                maxSum = sum;
                maxStart = start;
                maxLen = i - start + 1;
            }
        }

        return new int[]{maxSum, maxStart, maxLen};
    }
}

MaxSubSumTest.java:

(Test-Fall-über TestNG)

import org.testng.Assert;
import org.testng.annotations.Test;

import java.util.Arrays;

public class MaxSubSumTest {
    @Test
    public void test_find() {
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{ -2, -3, 4, -1, -2, 1, 5, -3}), new int[]{7, 2, 5})); //max sub array: {4, -1, -2, 1, 5}
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{12, 14, 0, -4, 61, -39}), new int[]{83, 0, 5})); //max sub array: {12, 14, 0, -4, 61}

        //corner
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{}), new int[]{0, 0, 0})); //empty array,

        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{ -5, -4, 0, 0, -7, 0, -2}), new int[]{0, 0, 0})); //array with all elements <= 0,
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{ -5, -4, -2, -7, -2, -9}), new int[]{0, 0, 0})); //array with all elements < 0,
    }

    @Test
    public void test_findIncludeNonPositive() {
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{ -2, -3, 4, -1, -2, 1, 5, -3}), new int[]{7, 2, 5})); //max sub array: {4, -1, -2, 1, 5}
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{12, 14, 0, -4, 61, -39}), new int[]{83, 0, 5})); //max sub array: {12, 14, 0, -4, 61}

        //corner
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{}), new int[]{0, 0, 0})); //empty array,

        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{ -5, -4, 0, 0, -7, 0, -2}), new int[]{0, 2, 1})); //array with all elements <= 0,
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{ -5, -4, -2, -7, -2, -9}), new int[]{ -2, 2, 1})); //array with all elements < 0,
    }
}

Erklärung:

• find()
  
  Finden Sie max sub-array, nur sub-array mit positiver Summe.
  
  Verhalten:

  • Für das array enthält nur nicht-positiven Elemente zu wählen, leere sub-Arrays beginnen von 0.
  • Für leere Eingabe-array zu wählen, leere sub-Arrays beginnen von 0.

  BTW:

  • Es neu starten, nur wenn ein positives element, und die Summe <= 0.

• findIncludeNonPositive()
  
  Finden Sie max sub-array enthalten auch sub-array mit nicht-positiven Summe.
  
  Verhalten:

  • Für das array enthält nur nicht-positive Elemente, wählen Sie zuerst kleinstes element.
  • Für leere Eingabe-array zu wählen, leere sub-Arrays beginnen von 0.

  BTW:

  • Es neu starten, Wann immer vorherigen Summe <= 0.
  • Es lieber sub-array starten von kleineren index, wenn es mehrere max sub-array.
  • Es wird nicht unnötig 0 am Ende der sub-array, das ändert nichts an der Summe.

Komplexität:

• Zeit: O(n)
• Raum: O(1)