Buscar la suma máxima de elementos en el conjunto

Escriba un programa que, mediante un conjunto de valores enteros (que contiene enteros negativos), encuentre la suma máxima de elementos sucesivos en el conjunto.Buscar la suma máxima de elementos en el conjunto

Ejemplo:

2, 3, -6, -1, 2, -1, 6, 4, -8, 8

Estoy buscando una solución que sea rápida r que O (N^2).

Fuente

2012-09-09 user1106337

1,2,5,6 no son sucesivos. Si no tiene ninguna restricción sobre el subconjunto que se puede tomar, este es el problema de suma de subconjuntos, que es NP-completo, pero no creo que sea el caso. – amit

Perdón por el malentendido. He cometido un error en la descripción y el ejemplo. :) He actualizado ambos. – user1106337

Un escaneo lineal puede resolver este problema. Simplemente resuma y compare con la corriente máxima, si la suma es <0, luego restaure la suma a 0 y continúe. Esta codiciosa solución ha demostrado ser correcta. Se llama algoritmo de Kadane: http://en.wikipedia.org/wiki/Maximum_subarray_problem – nhahtdh

Creo Kadane's Algorithm es lo que quiere

Fuente

2012-09-09 13:12:08 Qyrus

el enlace ya no es válido – fayyazkl

Esto es en realidad un problema de libros de texto que estudié en la universidad (Estructuras de datos y algoritmos en C por Mark Allen Weiss) ... Se trata de una solución y resuelve muy bonito y elegante en O (N)

int MaxSubsequenceSum(int A[]) 
{ 
    int sum = 0, maxSum = 0; 

    for (int j = 0; j < A.Length; j++) 
    { 
     sum = sum + A[j]; 

     if (sum > maxSum) 
      maxSum = sum ; 
     else if (sum < 0) 
      sum = 0; 
    } 
    return maxSum; 
}

Fuente

2012-09-09 14:08:08

Su publicación fue editada por un usuario anónimo y luego aprobada. ¿Podría confirmar que estos cambios son, de hecho, positivos? Parecía cambiar la lógica de manera significativa. – Gray

no No lo aprobé y tampoco mejoró significativamente la respuesta. Creo que se hizo para los puntos –

. Fue hecho por un usuario anónimo, por lo que no se otorgó ningún representante. Siéntase libre de retroceder. Ellos [dejaron un comentario] (http://stackoverflow.com/posts/12339772/revisions) sobre por qué lo hicieron. – Gray

-1

primer lugar, puede ordenar la matriz dada en orden descendente y, a continuación resumen los tres primeros elementos de la matriz por: sum=arr[0]+arr[1]+arr[2] por intializing la suma sum=0 y de impresión.

Fuente

2014-06-12 20:14:35 bitsk

Buscar la suma máxima de elementos en el conjunto

Respuesta

Cuestiones relacionadas