Encuentra la mayor suma de subsecuencia

Dada una secuencia de enteros, encuentre la suma más grande de una subsecuencia (enteros en posiciones consecutivas) de la secuencia. La subsecuencia puede estar vacía (en cuyo caso la suma es 0).

La entrada se lee desde la entrada estándar, un número entero por línea. La suma más grande debe escribirse en la salida estándar.

Escribí un pequeño generador para ti:

#include <stdio.h>
#include <assert.h>


/* From http://en.wikipedia.org/wiki/Random_number_generation */
unsigned m_w;
unsigned m_z;

unsigned get_random()
{
  m_z = 36969 * (m_z & 65535) + (m_z >> 16);
  m_w = 18000 * (m_w & 65535) + (m_w >> 16);
  return (m_z << 16) + m_w;  /* 32-bit result */
}

int main(int argc, char **argv)
{
  int i;

  assert(argc == 3);
  m_w = atoi(argv[1]);
  m_z = atoi(argv[2]);

  i = 10;
  while (i--);
    get_random();

  i = atoi(argv[2]);
  while (i--)
    printf("%d\n", (int) get_random() << 8 >> 22);

  return 0;
}

Ejemplos:

$ printf "1\n2\n-1\n4\n" | ./sum
6
$ printf "0\n-2\n-3\n" | ./sum
0

$ ./a.out 1 1 | ./sum
387
$ ./a.out 1 10 | ./sum
571
$ ./a.out 1 100 | ./sum
5867
$ ./a.out 1 1000 | ./sum
7531
$ ./a.out 1 10000 | ./sum
27268
$ ./a.out 1 100000 | ./sum
101332
$ ./a.out 1 1000000 | ./sum
187480
$ ./a.out 1 10000000 | ./sum
666307

• ./sum es mi solucion
• ./a.out es el generador

Su solución debe ejecutarse en un tiempo razonable para todas las pruebas anteriores (la mía se ejecuta en 1.2s en el último caso de prueba).

El código más corto gana.

Editar : proporcione un ejemplo ejecutado en una de las pruebas anteriores.

Ruby, 53 caracteres

p$<.inject(-1.0/s=0){|a,b|[s=[0,s+b.to_i].max,a].max}

Toma aproximadamente 28 segundos para el último caso de prueba aquí.

Python, 91 84 64 caracteres

s=m=0
try:
 while 1:s=max(s+input(),0);m=max(m,s)
except:print m

Toma alrededor de 14 12 72 segundos en el último caso de prueba. Editar: utilizando el algoritmo Paul R encontrado. Editar: rechazó la importación, usando input().

C, 100 caracteres

main(){char s[80];int i,m=0,n=0;while(gets(s)){i=atoi(s);n=n+i>0?n+i:0;m=m>n?m:n;}printf("%d\n",m);}

Tiempo de ejecución = 1.14 s para el caso de prueba final (10000000) en 2.67 GHz Core i7 con ICC 11.1 (anteriormente: 1.44 s con gcc 4.2.1).

Nota: El algoritmo utilizado para la solución anterior proviene de Programming Pearls de Jon Bentley. Aparentemente, este algoritmo se conoce como Algoritmo de Kadane .

Haskell ( 88 64)

Implementando el algoritmo de Kadane.

main=interact$show.maximum.scanr(\x->max x.(x+))0.map read.lines

Python - 114 caracteres

import sys
s=map(int,sys.stdin.readlines())
l=range(len(s)+1)
print`max(sum(s[i:j])for i in l[:-1]for j in l[i:])`

Seguramente no es tan rápido como se requiere, pero funciona bien.

Python, usando programación dinámica - 92 caracteres

import sys
s=map(int,sys.stdin.readlines())
f=h=0
for x in s:h=max(0,h+x);f=max(f,h)
print f

J ( 34 33 caracteres)

Esta solución implementa una variante del algoritmo de Kadane y es razonablemente rápida.

echo>./0,([>.+)/\.0".];._2(1!:1)3

Aquí hay una explicación:

• u/ y- El verbo u insertado entre elementos de y. Por ejemplo, +/ 1 2 3 4es como 1 + 2 + 3 + 4. Observe que todos los verbos en J están asociados a la derecha, es decir, -/ 1 2 3 4es como 1 - (2 - (3 - 4))y calcula la suma alterna de 1 2 3 4.
• x >. y- el máximo de xy y.
• x ([ >. +) y- El máximo de xy x + y. [ >. +es un verbo en notación tácita y se evalúa igual que x >. x + y.
• ([ >. +)/ y- el prefijo no vacío de ycon la suma más grande.
• u\. y- uaplicado a todos los sufijos de y. Observe que el código especial maneja el caso común de u/\. ytal manera que esto se ejecuta en tiempo lineal en lugar de cuadrático.
• ([ >. +)/\. y- Un vector que denota el subconjunto no vacío más grande que comienza en cada posición de y.
• 0 , ([ >. +)/\. y- 0preprendado al resultado anterior como 0es la longitud de un subconjunto vacío de y.
• >./ 0 , ([ >. +)/\. y- El subconjunto más grande de y.
• 0 ". ];._2 (1!:1) 3 - Entrada estándar convertida en un vector de números.
• >./ 0 , ([ >. +)/\. 0 ". ];._2 (1!:1) 3 - El subconjunto más grande en entrada estándar.

Ruby, 68 caracteres

m=-2**31;n=0;$<.lines.map{|x|n+=x.to_i;n=0 if n<0;m=n if n>m};puts m

También un poco lento, pero completa las pruebas 1-10000000 en poco más de medio minuto, la mayor parte del tiempo empleado en la última prueba ...

Versión sangrada:

m=-2**31
n=0
$<.lines.map {|x|
  n+=x.to_i
  n=0 if n<0
  m=n if n>m
}
puts m

C ++, 192 caracteres

#include <iostream>
#include <string>
#include <stdlib.h>
#define S std::
main(){long a=0,m=0,M=0;char s[9];while(S cin.getline(s,9)){a+=atoi(s);if(m>a)m=a;if(M<a-m)M=a-m;}S cout<<M<<S endl;}

Funciona razonablemente rápido en mi computadora portátil (4 segundos para la última prueba).

{if((r+$1)>0)
   r=r+$1 
 else r=0; 
 if(m<r) 
   m=r;
}
END{print m}

Código awk (66) , muy lento, más de 8 segundos para el último caso de prueba

dwang@dwang-ws ~/Playground/lss $ time ./random 1 10000000 | awk -f lss.awk
666307

real    0m6.705s
user    0m8.671s
sys 0m0.052s