Encontrar la subsecuencia con la suma más grande de elementos en una matriz

Question

Hace poco entrevisté con una empresa y me pidieron que escribiera un algoritmo que encuentre la subsecuencia con la suma más grande de elementos en una matriz. Los elementos en la matriz pueden ser negativos. ¿Hay una solución de O (n) para ello? Cualquier buena solución es muy apreciada.

Answer 1

Si desea que la mayor suma de números secuenciales entonces algo como esto podría funcionar:

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

Eso es justo al lado de la parte superior de mi cabeza, pero parece correcto. (Ignorando que asume 0 es la respuesta para los conjuntos vacíos y todos negativos.)

Editar:

Si también desea que la posición de la secuencia:

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

Puede haber una manera más concisa para hazlo. De nuevo, tiene las mismas suposiciones (al menos un entero positivo). Además, solo encuentra la primera secuencia más grande.

Editar: se cambió para usar max_j (exclusivo) en lugar de max_len.

Answer 2

supongo que te refieres más larga subsecuencia creciente.

No hay solución O(n) para eso.

Una solución muy ingenuo sería la creación de una matriz duplicada, una especie en O(NlogN) y luego encontrar el LCS de la matriz ordenada y matriz original que tiene O(N^2).

También hay una solución directa basada en DP similar a LCS que también toma O(N^2), que puede ver here.

Pero si se refiere a la secuencia de mayor duración (consecutiva). Esto se puede hacer en O(N).

Answer 3

Si quiere decir subsecuencia de mayor duración, vea codaddict's answer.

Si por el contrario te refieres a la búsqueda de la matriz sub con la máxima suma (sólo tiene sentido con valores negativos), entonces no es un estilo de programación dinámica solución elegante tiempo lineal:

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

Answer 4

función C es el siguiente:

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

Prueba el siguiente código:

#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

Este problema se puede resolver de dos maneras diferentes.

El primer enfoque es tener dos variables llamadas sum y MaxSum.

1. Vamos a seguir sumando los valores de la suma y la compararemos con la MaxSum, si el valor de la suma es mayor que el MaxSum - asignaremos valor de la suma a la MaxSum

2. Si durante el procese el valor de la suma por debajo de 0, restableceremos la suma y comenzaremos a agregar un nuevo número del próximo índice en pantalla. El código de ejemplo para la solución anterior se proporciona como a continuación:

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

El segundo enfoque para resolver este problema es que vamos a ir a través de todos y cada elemento de una matriz. Tendremos las mismas 2 variables de suma y MaxSum.

1. Primero compararemos la suma de suma con el siguiente elemento de matriz y la suma misma. Quien sea mayor, ese valor se almacenará en la variable de suma.

2. A continuación compararemos los valores de suma y MaxSum y quien tenga mayor valor, guardaremos ese valor en la variable MaxSum. El código de ejemplo es como se menciona a continuación:

   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 se está preguntando ¿qué es una subsecuencia contigua para los que la suma es máxima, he encontrado 4 algos hasta ahora: -

1. Brute-force: encuentra todas las sumas posibles utilizando ciclos anidados y sigue actualizando el maxSum si encuentras una suma mayor que el valor establecido anterior de maxSum. La complejidad del tiempo es O (n^2)

2. solución de programación dinámica: Se trata de una solución muy elegante que encontré en stackoverflow sí - https://stackoverflow.com/a/8649869/2461567v - Complejidad de tiempo: O (n), la complejidad Espacio: O (n)

3. DP sin memoria - kadane Algoritmo - https://en.wikipedia.org/wiki/Maximum_subarray_problem - complejidad de tiempo: O (n), la complejidad de las instalaciones: O (1)

4. Divide y Solución Conquer - http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdf complejidad de tiempo: O (NLGN)