Revizia anterioară Revizia următoare
Here is a wiki page that shows the bugs described in ticket 410
This works: &page=anything
This doesn't work: &page=anything
This doesn't work:
Construim întâi şirul sumelor parţiale. Pentru oricare două elemente sum[i] şi sum[j] cu (i != j) modulul sumei unei subsecvenţe din şir va fi |sum[i] - sum[j]|. Dacă i < j, atunci secvenţa va fi a[i+1..j], iar dacă j < i, atunci secvenţa va fi a[j+1 .. i]. Astfel, pentru a găsi subsecvenţa de modul minim trebuie, de fapt, să găsim perechea de indici i şi j astfel ca |sum[i] - sum[j]| să fie minim. Sortând şirul sumelor parţiale şi luând o pereche de indici i < j, atunci sum[i] < sum[j], iar |sum[j] - sum[i]| = sum[j] - sum[i]. Pentru a găsi perechea (i, j) pentru care i < j şi sum[j] - sum[i] este minim, trebuie ca i să fie egal cu j + 1. Astfel obţinem un algoritm de complexitate O(N * log N).
