Trouver la sous-séquence avec la plus grande somme d'éléments dans un tableau

Question

J'ai récemment interviewé une entreprise et ils m'ont demandé d'écrire un algorithme qui trouve la sous-séquence avec la plus grande somme d'éléments dans un tableau. Les éléments du tableau peuvent être négatifs. Y a-t-il une solution O (n) pour cela? Toutes les bonnes solutions sont très appréciées.

Answer 1

Si vous voulez la plus grande somme de numéros séquentiels alors quelque chose comme cela pourrait fonctionner:

$cur = $max = 0; 
foreach ($seq as $n) 
{ 
    $cur += $n; 
    if ($cur < 0) $cur = 0; 
    if ($cur > $max) $max = $cur; 
} 

C'est juste à côté du haut de ma tête, mais il semble juste. (Ignorant qu'il suppose 0 est la réponse pour vide et tous les jeux négatifs.)

Edit:

Si vous voulez aussi la position de séquence:

$cur = $max = 0; 
$cur_i = $max_i = 0; 
$max_j = 1; 

foreach ($seq as $i => $n) 
{ 
    $cur += $n; 
    if ($cur > $max) 
    { 
    $max = $cur; 
    if ($cur_i != $max_i) 
    { 
     $max_i = $cur_i; 
     $max_j = $max_i + 1; 
    } 
    else 
    { 
     $max_j = $i + 1; 
    } 
    } 

    if ($cur < 0) 
    { 
    $cur = 0; 
    $cur_i = $i + 1; 
    } 
} 

var_dump(array_slice($seq, $max_i, $max_j - $max_i), $max); 

Il pourrait y avoir une façon plus concise fais le. Encore une fois, il a les mêmes hypothèses (au moins un entier positif). En outre, il ne trouve que la première plus grande séquence. Editer: modifié pour utiliser max_j (exclusif) au lieu de max_len.

Answer 2

Je suppose que vous voulez dire plus longue sous-séquence croissante. Il n'existe pas de solution O(n) pour cela.

Une solution très naïve serait de créer un tableau dupliqué, le trier en O(NlogN) et ensuite trouver le LCS du tableau trié et tableau original qui prend O(N^2).

Il existe également une solution directe basée sur DP similaire à LCS qui prend également O(N^2), que vous pouvez voir here.

Mais si vous voulez dire la plus longue séquence croissante (consécutive). Cela peut être fait en O(N).

Answer 3

Si vous voulez dire plus longue sous-séquence croissante, voir codaddict réponse.

Si d'autre part vous voulez dire trouver le tableau sous avec la somme maximale (n'a de sens que des valeurs négatives), alors il y a un style de programmation élégante, dynamique solution de temps linéaire:

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Answer 4

fonction C ressemble à ceci:

int largest(int arr[], int length) 
{ 
    int sum= arr[0]; 
    int tempsum=0; 
    for(int i=0;i<length;i++){ 
    tempsum+=arr[i]; 
    if(tempsum>sum) 
     sum=tempsum; 
    if(tempsum<0) 
     tempsum=0; 
    } 
    return sum; 
} 

Answer 5

Essayez le code suivant:

#include <stdio.h> 

int main(void) { 
    int arr[] = {-11,-2,3,-1,2,-9,-4,-5,-2, -3}; 
    int cur = arr[0] >= 0? arr[0] : 0, max = arr[0]; 
    int start = 0, end = 0; 
    int i,j = cur == 0 ? 1 : 0; 
    printf("Cur\tMax\tStart\tEnd\n"); 
    printf("%d\t%d\t%d\t%d\n",cur,max,start,end); 
    for (i = 1; i < 10; i++) { 
     cur += arr[i]; 
     if (cur > max) { 
      max = cur; 
      end = i; 
      if (j > start) start = j; 
     }  
     if (cur < 0) { 
      cur = 0; 
      j = i+1; 
     } 
     printf("%d\t%d\t%d\t%d\n",cur,max,start,end); 
    } 
    getchar(); 
} 

Answer 6

void longsub(int a[], int len) { 

     int localsum = INT_MIN; 
     int globalsum = INT_MIN; 
     int startindex = 0,i=0; 
     int stopindex = 0; 
     int localstart = 0; 

     for (i=0; i < len; i++) { 
       if (localsum + a[i] < a[i]) { 
         localsum = a[i]; 
         localstart = i; 
       } 
       else { 
         localsum += a[i]; 
       } 

       if (localsum > globalsum) { 
         startindex = localstart; 
         globalsum = localsum; 
         stopindex = i; 
       } 

     } 

     printf ("The begin and end indices are %d -> %d (%d).\n",startindex, stopindex, globalsum); 

} 

Answer 7

Ce problème peut être résolu de deux manières différentes.

La première approche a deux variables appelées sum et MaxSum.

1. Nous allons continuer à ajouter des valeurs à la somme et comparerons avec le maxsum, si la valeur de la somme est supérieure à la maxsum - va attribuer une valeur de somme au maxsum

2. Si au cours de la traiter la valeur pour que la somme passe en dessous de 0, nous allons réinitialiser la somme et commencerons à ajouter un nouveau numéro à partir de l'index suivant. L'exemple de code pour la solution ci-dessus est fourni ci-dessous:

   private static void FindMaxSum(int[] array) 
   { 
       int sum = 0; 
       int MaxSum = 0; 
   
       for (int i = 0; i < array.Length; i++) 
       { 
        sum += array[i]; 
   
        if (sum > MaxSum) 
        { 
         MaxSum = sum; 
        } 
        else if (sum < 0) 
        { 
         sum = 0; 
        } 
       } 
       Console.WriteLine("Maximum sum is: " + MaxSum); 
   } 
   

La seconde approche pour résoudre ce problème est que nous allons passer par chaque élément dans un tableau. Nous aurons les mêmes 2 variables de somme et MaxSum.

1. Nous allons d'abord comparer l'addition de sum avec l'élément de tableau suivant et la somme elle-même. Qui est le plus grand - cette valeur sera stockée dans la variable somme.

2. Ensuite, nous allons comparer les valeurs de sum et MaxSum et celui qui a la plus grande valeur - nous allons enregistrer cette valeur dans la variable MaxSum. L'exemple de code est tel que mentionné ci-dessous:

   private static void FindMaxSum(int[] array) 
   { 
       int sum = array[0], Maxsum = array[0]; 
   
       for (int i = 1; i < array.Length; i++) 
       { 
        sum = Max(sum + array[i], array[i]); 
        Maxsum = Max(sum, Maxsum);    
       } 
   
       Console.WriteLine("Maximum sum is: " + Maxsum); 
   } 
   
   private static int Max(int a, int b) 
   { 
       return a > b ? a : b; 
   } 
   

Answer 8

Si vous demandez ce qui est une sous contiguës dont la somme est maximale, j'ai trouvé 4 algos jusqu'à présent: -

1. Brute-force: Trouvez toutes les sommes possibles en utilisant des boucles imbriquées et continuez à mettre à jour le maxSum si vous trouvez une somme supérieure à la valeur précédente de maxSum. La complexité est en O (n^2)

2. Programmation dynamique Solution: Ceci est une solution remarquablement élégante que je trouve sur StackOverflow lui-même - https://stackoverflow.com/a/8649869/2461567v - complexité Temps: O (n), complexité de l'espace: O (n)

3. DP sans mémoire - Kadane algorithme - https://en.wikipedia.org/wiki/Maximum_subarray_problem - complexité Temps: O (n), la complexité de l'espace: O (1)

4. Divide and Conquer Solution - http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdf complexité Temps: O (NLGN)