algorithm
Algoritmo di sottarray massimo

Algoritmo di subarray massimo Informazioni di base

Il massimo problema di sottoarray è il metodo per trovare il sottoarray contiguo all'interno di una matrice unidimensionale di numeri che ha la somma maggiore.

Il problema fu originariamente proposto da Ulf Grenander della Brown University nel 1977, come modello semplificato per la stima della massima verosimiglianza dei pattern nelle immagini digitalizzate.

Possiamo avere un problema come questo, consideriamo una lista di vari numeri interi. Potremmo essere interessati a quale sottoinsieme completamente adiacente avrà la somma maggiore. Ad esempio, se abbiamo l'array [0, 1, 2, -2, 3, 2] , il subarray massimo è [3, 2] , con una somma di 5 .

Approccio alla forza bruta per la soluzione:

Questo metodo è il più inefficiente per scoprire la soluzione. In questo, finiremo per passare attraverso ogni singolo sottoarray possibile, e quindi trovare la somma di tutti loro. Alla fine, confronta tutti i valori e scopri il massimo sottoarray.

Pseudo codice per l'approccio Brute-Force:

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

La complessità del tempo per il metodo Brute-Force è O(n^2) . Quindi passiamo a dividere e conquistare l'approccio.

Divide and Conquer Approach for Solution:

Trova la somma dei subarray sul lato sinistro, i sotto-righe a destra. Quindi, dai un'occhiata a tutti quelli che attraversano la divisione centrale e infine restituisci la somma massima. Poiché si tratta di un algoritmo di divisione e conquista, è necessario disporre di due funzioni diverse.

La prima è la divisione,

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

Nella seconda parte, separa la parte diversa che viene creata nella prima parte.

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

La complessità temporale per il metodo Divide and Conquer è O(nlogn) . Passiamo quindi all'approccio di programmazione dinamica.

Approccio alla programmazione dinamica:

Questa soluzione è anche conosciuta come Algoritmo di Kadane. È un algoritmo di tempo lineare. Questa soluzione è stata data da Joseph B. Kadane alla fine degli anni '70.

Questo algoritmo passa semplicemente attraverso il ciclo, modificando continuamente la somma massima corrente. È interessante notare che questo è un esempio molto semplice di un algoritmo di programmazione dinamica, poiché richiede un problema di sovrapposizione e lo riduce in modo da poter trovare una soluzione più efficiente.

Pseudo codice dell'algoritmo di 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

La complessità temporale per Algoritmo di Kadane è O(n) .

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