Trouver la plus grande somme de sous-séquences

Étant donné une séquence d'entiers, trouvez la plus grande somme d'une sous-séquence (entiers sur des positions consécutives) de la séquence. La sous-séquence peut être vide (auquel cas la somme est 0).

L'entrée est lue à partir de l'entrée standard, un entier par ligne. La plus grande somme doit être écrite sur la sortie standard.

J'ai écrit un petit générateur pour vous:

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

Exemples:

$ 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 est ma solution
• ./a.out est le générateur

Votre solution doit s'exécuter dans un délai raisonnable pour tous les tests ci-dessus (la mienne s'exécute en 1.2s sur le dernier scénario de test).

Le code le plus court gagne.

Modifier : veuillez fournir un exemple exécuté sur l'un des tests ci-dessus.

Ruby, 53 caractères

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

Cela prend environ 28 secondes pour le dernier test ici.

Python, 91 84 64 caractères

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

Prend environ 14 12 72 secondes sur le dernier cas de test. Edit: en utilisant l'algorithme Paul R trouvé. Edit: annulé l'importation, en utilisant input().

C, 100 caractères

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

Temps d' exécution = 1,14 s pour le cas de test final (10000000) sur le Core i7 à 2,67 GHz avec ICC 11.1 (auparavant: 1,44 s avec gcc 4.2.1).

Remarque: l'algorithme utilisé pour la solution ci-dessus provient de Programming Pearls de Jon Bentley. Apparemment, cet algorithme est connu sous le nom d'algorithme de Kadane .

Haskell ( 88 64)

Implémentation de l'algorithme de Kadane.

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

Python - 114 caractères

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:])`

Ce n'est sûrement pas aussi rapide que nécessaire, mais cela fonctionne bien.

Python, utilisant la programmation dynamique - 92 caractères

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 caractères)

Cette solution implémente une variante de l'algorithme de Kadane et est relativement rapide.

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

Voici une explication:

• u/ y- Le verbe u inséré entre les éléments de y. Par exemple, +/ 1 2 3 4c'est comme 1 + 2 + 3 + 4. Notez que tous les verbes de J sont associés à droite, c'est-à-dire -/ 1 2 3 4est similaire 1 - (2 - (3 - 4))et calcule la somme alternée de 1 2 3 4.
• x >. y- le maximum de xet y.
• x ([ >. +) y- Le maximum de xet x + y. [ >. +est un verbe en notation tacite et a la même valeur que x >. x + y.
• ([ >. +)/ y- le préfixe non vide de yavec la plus grande somme.
• u\. y- uappliqué à tous les suffixes de y. Notez que le code spécial gère le cas commun de u/\. ytelle sorte qu'il s'exécute en temps linéaire plutôt qu'en temps quadratique.
• ([ >. +)/\. y- Un vecteur indiquant le plus grand sous-tableau non vide qui commence à chaque position de y.
• 0 , ([ >. +)/\. y- 0précédé du résultat précédent, tout comme 0la longueur d'un sous-tableau vide de y.
• >./ 0 , ([ >. +)/\. y- Le plus grand sous-tableau de y.
• 0 ". ];._2 (1!:1) 3 - Entrée standard organisée en un vecteur de nombres.
• >./ 0 , ([ >. +)/\. 0 ". ];._2 (1!:1) 3 - Le plus grand sous-tableau en entrée standard.

Rubis, 68 caractères

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

Également un peu lent, mais termine les tests 1-10000000 en un peu plus d'une demi-minute, la plupart du temps passé dans le dernier test ...

Version en retrait:

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 caractères

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

Fonctionne assez rapidement sur mon ordinateur portable (4 secondes pour le dernier test).

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

awk Code (66) , très lent, 8+ secondes pour le dernier cas de test

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

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