algorithm
Maximaal subarray-algoritme

Maximale subarray-algoritme Basisinformatie

Maximaal subarray-probleem is de methode om de aaneengesloten subarray te vinden binnen een eendimensionale reeks getallen met de grootste som.

Het probleem werd oorspronkelijk voorgesteld door Ulf Grenander van Brown University in 1977, als een vereenvoudigd model voor maximale waarschijnlijkheidsinschatting van patronen in gedigitaliseerde afbeeldingen.

We kunnen dit probleem oplossen, laten we een lijst met verschillende gehele getallen bekijken. We zijn misschien geïnteresseerd in welke volledig aangrenzende subset de grootste som heeft. Als we bijvoorbeeld de array [0, 1, 2, -2, 3, 2] , is de maximale subarray [3, 2] , met een som van 5 .

Brute-Force aanpak voor oplossing:

Deze methode is het meest inefficiënt om de oplossing te vinden. In dit zullen we door elke mogelijke subarray gaan en dan de som van alle vinden. Vergelijk ten slotte alle waarden en ontdek maximale subarray.

Pseudo-code voor 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

Tijdcomplexiteit voor de Brute-Force-methode is O(n^2) . Dus laten we verdergaan om de benadering te verdelen en te overwinnen.

Verdeel en heers aanpak voor oplossing:

Zoek de som van de subreeksen aan de linkerkant, de subreeksen aan de rechterkant. Neem vervolgens een kijkje door al diegenen die over de middenverdeling gaan en geef uiteindelijk de maximale som terug. Omdat dit een verdeel en heers algoritme is, moeten we twee verschillende functies hebben.

Eerst is verdeel stap,

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))

In het tweede deel, scheidt u de verschillende delen die in het eerste deel zijn gemaakt.

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

De tijdcomplexiteit voor de methode Divide and Conquer is O(nlogn) . Laten we dus overgaan op een dynamische programmeerbenadering.

Dynamische programmeerbenadering:

Deze oplossing wordt ook wel het algoritme van Kadane genoemd. Het is een lineair tijdalgoritme. Deze oplossing wordt eind jaren 70 gegeven door Joseph B. Kadane .

Dit algoritme gaat gewoon door de lus en verandert continu de huidige maximale som. Interessant genoeg is dit een heel eenvoudig voorbeeld van een dynamisch programmeeralgoritme, omdat er een overlappend probleem voor nodig is en dit wordt verkleind, zodat we een efficiëntere oplossing kunnen vinden.

Pseudo-code van het algoritme van Kadane:

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

Tijdcomplexiteit voor het algoritme van Kadane is O(n) .

C # Implementatie

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);
    }
}