Witam
Potrzebuję algorytmu który, pomoże mi z takim problemem. Mam plik, w pierwszym wierszu jest podana ilość liczb, a w kolejnych te liczby. Potrzebuje algorytmu, który znajdzie największą możliwą sumę pomiędzy liczbami, i powie od liczby z jakim indeksem zaczynają się liczby składające się na tą sumę i na jakiej kończą. Fajnie by było jakby ktoś podał jakąś naiwną wersję, gdzie potrzebujesz dużej mocy obliczeniowej i algorytm, który jest najbardziej wydajny.
Z góry dziękuje
0
2
Co to jest „suma pomiędzy liczbami”?
0
Chodzi mi o coś takiego
dajmy na to mamy liczby: 1, 5, -3, 4, 6, 1, 3, -8
i znajduje mi największą sumę czyli w tym wypadku 14, zaczyna się na indeksie 3 a kończy na 6
3
Althorion napisał(a):
Co to jest „suma pomiędzy liczbami”?
No np.: 2, 
, 3
To w środku to właśnie suma pomiędzy liczbami. Mam nadzieję, że pomogłem.
A poza tym, to SZCZUPAK TO JEST KRÓL WODY JAK LEW JEST KRÓL DŻUNGLI
@welik2: ten temat to ogłoszenie drobne czy próba wyłudzenia gotowca? Bo nie wiem gdzie przenieść...
3
Ach. To chodzi Ci o maksymalną sumę podciągu spójnego. To, z tego co wiem, optymalnym rozwiązaniem jest tutaj algorytm Kadane, a jako przeciwieństwa możesz użyć po prostu brute force’a (złożoność kwadratowa, analizujesz wszystkie podciągi zaczynające się od indeksu zero, od indeksu jeden itd.).