algorithm
Maximal subbarray-algoritm

Grundläggande information om maximal subbarrayalgoritm

Maximalt subarrayproblem är metoden för att hitta den sammanhängande delgruppen inom en endimensionell grupp med nummer som har den största summan.

Problemet föresloges ursprungligen av Ulf Grenander från Brown University 1977 som en förenklad modell för maximal uppskattning av mönster i digitaliserade bilder.

Vi kan problem så här, låt oss ta en lista över olika heltal. Vi kanske är intresserade av vilken helt angränsande delmängd kommer att ha den största summan. Om vi till exempel har matrisen [0, 1, 2, -2, 3, 2] , är den maximala subarrayen [3, 2] , med summan 5 .

Brute-Force-strategi för lösning:

Denna metod är mest ineffektiv för att ta reda på lösningen. I detta kommer vi till slut att gå igenom varje möjlig delgrupp och sedan hitta summan av dem alla. Slutligen, jämföra alla värden och ta reda på maximal undergrupp.

Pseudokod för 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

Tidskomplexitet för Brute-Force-metoden är O(n^2) . Så låt oss gå och dela och erövra strategi.

Dela och erövra strategi för lösning:

Hitta summan av subarrays på vänster sida, subarrays till höger. Sedan kan du titta igenom alla de som kryssar över mittdelningen och slutligen returnera den maximala summan. Eftersom detta är en splittring och erövringsalgoritm, måste vi ha två olika funktioner.

Först är splittringssteg,

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

I den andra delen, separera den olika delen som skapas i första delen.

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

Tidskomplexiteten för metoden Divide and Conquer är O(nlogn) . Så låt oss gå till dynamisk programmeringsmetod.

Dynamisk programmeringsstrategi:

Denna lösning är också känd som Kadanes algoritm. Det är linjär tidsalgoritm. Denna lösning ges av Joseph B. Kadane i slutet av 70-talet.

Denna algoritm går bara genom loopen och ändrar kontinuerligt den aktuella maximala summan. Intressant nog är detta ett mycket enkelt exempel på en dynamisk programmeringsalgoritm, eftersom det tar ett överlappande problem och minskar det så att vi kan hitta en mer effektiv lösning.

Pseudokod för Kadanes algoritm:

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

Tidskomplexiteten för Kadanes algoritm är O(n) .

C # Implementering

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