Finden Sie die größte Summe der Teilsequenzen

Bei einer gegebenen Folge von ganzen Zahlen finden Sie die größte Summe einer Teilsequenz (ganze Zahlen an aufeinanderfolgenden Positionen) der Folge. Die Teilsequenz kann leer sein (in diesem Fall ist die Summe 0).

Die Eingabe wird von der Standardeingabe gelesen, eine Ganzzahl pro Zeile. Die größte Summe muss in die Standardausgabe geschrieben werden.

Ich habe einen kleinen Generator für Sie geschrieben:

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

Beispiele:

$ 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 ist meine Lösung
• ./a.out ist der Generator

Ihre Lösung muss für alle oben genannten Tests in angemessener Zeit ausgeführt werden (meine läuft im letzten Testfall in 1,2 Sekunden).

Der kürzeste Code gewinnt.

Bearbeiten : Bitte geben Sie ein Beispiel für einen der oben genannten Tests an.

Ruby, 53 Zeichen

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

Der letzte Testfall dauert hier ungefähr 28 Sekunden.

Python, 91 84 64 Zeichen

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

Dauert beim letzten Testfall ca. 14 12 72 Sekunden. Bearbeiten: mit Algorithmus Paul R gefunden. Bearbeiten: Der Import wurde mit nixed input().

C, 100 Zeichen

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

Laufzeit = 1,14 s für den endgültigen Testfall (10000000) auf 2,67 GHz Core i7 mit ICC 11.1 (zuvor: 1,44 s mit gcc 4.2.1).

Hinweis: Der für die obige Lösung verwendete Algorithmus stammt von Programming Pearls von Jon Bentley. Anscheinend ist dieser Algorithmus als Kadanes Algorithmus bekannt .

Haskell ( 88 64)

Implementierung des Kadane-Algorithmus.

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

Python - 114 Zeichen

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

Es ist sicherlich nicht so schnell wie erforderlich, aber es funktioniert in Ordnung.

Python mit dynamischer Programmierung - 92 Zeichen

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 Zeichen)

Diese Lösung implementiert eine Variante des Kadane-Algorithmus und ist relativ schnell.

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

Hier ist eine Erklärung:

• u/ y- Das zwischen Elementen von u eingefügte Verb y. ZB +/ 1 2 3 4ist wie 1 + 2 + 3 + 4. Beachten Sie, dass alle Verben in J rechtsassoziiert sind, dh -/ 1 2 3 4wie sind 1 - (2 - (3 - 4))und die alternierende Summe von berechnen 1 2 3 4.
• x >. y- das Maximum von xund y.
• x ([ >. +) y- Das Maximum von xund x + y. [ >. +ist ein Verb in stillschweigender Notation und wird gleich bewertet wie x >. x + y.
• ([ >. +)/ y- das nicht leere Präfix von ymit der größten Summe.
• u\. y- uangewendet auf alle Suffixe von y. Beachten Sie, dass spezieller Code den allgemeinen Fall u/\. yso behandelt, dass dieser in linearer statt quadratischer Zeit ausgeführt wird.
• ([ >. +)/\. y- Ein Vektor, der das größte nicht leere Subarray bezeichnet, das an jeder Position von beginnt y.
• 0 , ([ >. +)/\. y- 0dem vorherigen Ergebnis vorangestellt, ebenso 0wie die Länge eines leeren Subarrays von y.
• >./ 0 , ([ >. +)/\. y- Das größte Subarray von y.
• 0 ". ];._2 (1!:1) 3 - Standardeingabe in einem Vektor von Zahlen zusammengefasst.
• >./ 0 , ([ >. +)/\. 0 ". ];._2 (1!:1) 3 - Das größte Subarray in der Standardeingabe.

Ruby, 68 Zeichen

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

Auch etwas langsam, aber führt die 1-10000000-Tests in etwas mehr als einer halben Minute durch, die meiste Zeit im letzten Test ...

Eingedrückte Version:

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 Zeichen

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

Funktioniert relativ schnell auf meinem Laptop (4 Sekunden für den letzten Test).

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

awk Code (66) , sehr langsam, 8+ Sekunden für den letzten Testfall

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

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