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.
code-golf
subsequence
Alexandru
źródło
źródło
#include <stdlib.h>
zaatoi()
.while (i--);
nie powinien kończyć się średnikiem, prawda?Odpowiedzi:
Ruby, 53 znaki
Ostatni test testowy zajmuje około 28 sekund.
źródło
Python,
918464 znakówOstatni test trwa około
141272 sekund. Edycja: za pomocą algorytmu znaleziono Paul R. Edycja: nixed import, używającinput()
.źródło
C, 100 znaków
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 .
źródło
Haskell (
8864)Implementacja algorytmu Kadane.
źródło
Python - 114 znaków
Z pewnością nie jest tak szybki, jak to wymagane, ale działa dobrze.
źródło
Python, wykorzystujący programowanie dynamiczne - 92 znaki
źródło
J (
3433 znaki)To rozwiązanie implementuje wariant algorytmu Kadane i jest dość szybkie.
Oto wyjaśnienie:
u/ y
- Czasowniku
wstawiony między pozycjey
. Np.+/ 1 2 3 4
Jest jak1 + 2 + 3 + 4
. Zauważ, że wszystkie czasowniki w J są powiązane z prawą, to znaczy-/ 1 2 3 4
są podobne1 - (2 - (3 - 4))
i obliczają przemienną sumę1 2 3 4
.x >. y
- maksimumx
iy
.x ([ >. +) y
- maksimumx
ix + y
.[ >. +
jest czasownikiem w milczącej notacji i działa tak samo jakx >. x + y
.([ >. +)/ y
- niepusty prefiksy
z największą sumą.u\. y
-u
zastosowane do wszystkich przyrostkówy
. Zauważ, że specjalny kod obsługuje zwykły przypadeku/\. y
, który działa liniowo zamiast kwadratowo.([ >. +)/\. y
- Wektor oznaczający największą niepustą podtablicę, która zaczyna się w każdej pozycjiy
.0 , ([ >. +)/\. y
-0
wstępnie przygotowany do poprzedniego wyniku, podobnie jak0
długość pustej podtablicy o wartościy
.>./ 0 , ([ >. +)/\. y
- Największa podtablicay
.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.źródło
Ruby, 68 znaków
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:
źródło
C ++, 192 znaki
Działa dość szybko na moim laptopie (4 sekundy do ostatniego testu).
źródło
cstdlib
niestdlib.h
kod awk (66) , bardzo wolny, ponad 8 sekund dla ostatniego przypadku testowego
źródło