algorithm
Algorytm maksymalnej podtablicy

Podstawowe informacje na temat algorytmu maksymalnej podtablicy

Problemem maksymalnej podtablicy jest metoda znajdowania ciągłej podtablicy w jednowymiarowej tablicy liczb, która ma największą sumę.

Problem został pierwotnie zaproponowany przez Ulfa Grenandera z Uniwersytetu Browna w 1977 r. Jako uproszczony model szacowania maksymalnego prawdopodobieństwa wzorców na zdigitalizowanych obrazach.

Możemy mieć taki problem, rozważmy listę różnych liczb całkowitych. Możemy być zainteresowani tym, który całkowicie sąsiadujący podzbiór będzie miał największą sumę. Na przykład, jeśli mamy tablicę [0, 1, 2, -2, 3, 2] , maksymalna podtablica wynosi [3, 2] , z sumą 5 .

Podejście Brute-Force do rozwiązania:

Ta metoda jest najbardziej nieefektywna w znalezieniu rozwiązania. W ten sposób przejdziemy przez każdą możliwą podtablicę, a następnie znajdziemy sumę wszystkich z nich. Na koniec porównaj wszystkie wartości i znajdź maksymalną podtablicę.

Pseudo-kod dla Brute-Force Approach:

MaxSubarray(array)
  maximum = 0
  for i in input
    current = 0
    for j in input
       current += array[j]
       if current > maximum
         maximum = current
  return maximum

Złożoność czasowa dla metody Brute-Force wynosi O(n^2) . Przejdźmy więc do dzielenia i podbijania podejścia.

Podejmij podział i podbij rozwiązanie:

Znajdź sumę podrzędnych po lewej stronie, podrzędnych po prawej. Następnie przejrzyj wszystkie te, które przekraczają podział środkowy, i na koniec zwróć maksymalną sumę. Ponieważ jest to algorytm dzielenia i zdobywania, musimy mieć dwie różne funkcje.

Pierwszy to krok dzielenia,

maxSubarray(array)
  if start = end
    return array[start]
  else
    middle = (start + end) / 2
    return max(maxSubarray(array(From start to middle)), maxSubarray(array(From middle + 1 to end)), maxCrossover(array))

W drugiej części oddziel różne części, które są tworzone w pierwszej części.

maxCrossover(array)
  currentLeftSum = 0
      leftSum = 0
  currentRightSum = 0
      rightSum = 0
  for i in array
    currentLeftSum += array[i]
    if currentLeftSum > leftSum
      leftSum = currentLeftSum
  for i in array
    currentRightSum += array[i]
    if currentRightSum > rightSum
      rightSum = currentRightSum
  return leftSum + rightSum

Złożoność czasowa dla metody Dziel i rządź wynosi O(nlogn) . Przejdźmy więc do programowania dynamicznego.

Dynamiczne podejście do programowania:

To rozwiązanie jest również znane jako Algorytm Kadane'a. Jest to liniowy algorytm czasu. To rozwiązanie podaje Joseph B. Kadane pod koniec lat 70.

Ten algorytm po prostu przechodzi przez pętlę, ciągle zmieniając bieżącą maksymalną sumę. Co ciekawe, jest to bardzo prosty przykład algorytmu programowania dynamicznego, ponieważ wymaga nakładającego się problemu i zmniejsza go, abyśmy mogli znaleźć bardziej wydajne rozwiązanie.

Pseudo-kod algorytmu Kadane'a:

MaxSubArray(array)
  max = 0
  currentMax = 0
  for i in array
    currentMax += array[i]
    if currentMax < 0
      currentMax = 0
    if max < currentMax
      max = currentMax
  return max

Złożoność czasowa algorytmu Kadane'a wynosi O(n) .

Implementacja C #

public class MaximumSubarray
{
    private static int Max(int a, int b)
    {
        return a > b ? a : b;
    }

    static int MaxSubArray(int[] input, int n)
    {
        int max = input[0];
        int currentMax = input[0];
        for (int i = 1; i < n; i++)
        {
            currentMax = Max(input[i], currentMax + input[i]);
            max = Max(max, currentMax);
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return MaxSubArray(input, n);
    }
}