Znajdź największą sumę podsekwencji

Biorąc pod uwagę sekwencję liczb całkowitych, znajdź największą sumę podsekwencji (liczby całkowite na kolejnych pozycjach) sekwencji. Podsekwencja może być pusta (w takim przypadku suma wynosi 0).

Wejście jest odczytywane ze standardowego wejścia, jedna liczba całkowita na linię. Największa suma musi być zapisana na standardowe wyjście.

Napisałem dla ciebie mały generator:

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

Przykłady:

$ 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 to moje rozwiązanie
• ./a.out jest generatorem

Twoje rozwiązanie musi zostać uruchomione w rozsądnym czasie dla wszystkich powyższych testów (moje działa w 1,2 sekundy w ostatnim przypadku testowym).

Najkrótszy kod wygrywa.

Edycja : Podaj przykładowy przebieg jednego z powyższych testów.

Ruby, 53 znaki

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

Ostatni test testowy zajmuje około 28 sekund.

Python, 91 84 64 znaków

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

Ostatni test trwa około 14 12 72 sekund. Edycja: za pomocą algorytmu znaleziono Paul R. Edycja: nixed import, używając input().

C, 100 znaków

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

Czas pracy = 1,14 s dla końcowego przypadku testowego (10000000) na 2,67 GHz Core i7 z ICC 11.1 (wcześniej: 1,44 s z gcc 4.2.1).

Uwaga: Algorytm zastosowany w powyższym rozwiązaniu pochodzi z Programming Pearls autorstwa Jona Bentleya. Najwyraźniej ten algorytm jest znany jako Algorytm Kadane'a .

Haskell ( 88 64)

Implementacja algorytmu Kadane.

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

Python - 114 znaków

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

Z pewnością nie jest tak szybki, jak to wymagane, ale działa dobrze.

Python, wykorzystujący programowanie dynamiczne - 92 znaki

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

To rozwiązanie implementuje wariant algorytmu Kadane i jest dość szybkie.

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

Oto wyjaśnienie:

• u/ y- Czasownik u wstawiony między pozycje y. Np. +/ 1 2 3 4Jest jak 1 + 2 + 3 + 4. Zauważ, że wszystkie czasowniki w J są powiązane z prawą, to znaczy -/ 1 2 3 4są podobne 1 - (2 - (3 - 4))i obliczają przemienną sumę 1 2 3 4.
• x >. y- maksimum xi y.
• x ([ >. +) y- maksimum xi x + y. [ >. +jest czasownikiem w milczącej notacji i działa tak samo jak x >. x + y.
• ([ >. +)/ y- niepusty prefiks yz największą sumą.
• u\. y- uzastosowane do wszystkich przyrostków y. Zauważ, że specjalny kod obsługuje zwykły przypadek u/\. y, który działa liniowo zamiast kwadratowo.
• ([ >. +)/\. y- Wektor oznaczający największą niepustą podtablicę, która zaczyna się w każdej pozycji y.
• 0 , ([ >. +)/\. y- 0wstępnie przygotowany do poprzedniego wyniku, podobnie jak 0długość pustej podtablicy o wartości y.
• >./ 0 , ([ >. +)/\. y- Największa podtablica y.
• 0 ". ];._2 (1!:1) 3 - Standardowe wejście zestawione w wektor liczb.
• >./ 0 , ([ >. +)/\. 0 ". ];._2 (1!:1) 3 - Największa podtablica na standardowym wejściu.

Ruby, 68 znaków

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

Również trochę powolny, ale wykonuje testy 1-10000000 w nieco ponad pół minuty, większość czasu spędzonego na ostatnim teście ...

Wersja wcięta:

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 znaki

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

Działa dość szybko na moim laptopie (4 sekundy do ostatniego testu).

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

kod awk (66) , bardzo wolny, ponad 8 sekund dla ostatniego przypadku testowego

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

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