Mamy tablicę wartości typu int, przechowującą liczby zarówno dodatnie jak i ujemne. Trzeba wyznaczyć sumę dwóch największych (których suma jest największa, najbardziej optymalna) podzbiorów, nie posiadające części wspólnej (chodzi o to, żeby nie wykorzystywać elementów o tym samym indeksie). Jeden podzbiór musi zaczynać się od początku, drugi od końca. Przy czym podzbiór może być pusty (np gdy wszystkie elementy dałyby największą możliwą sumę gdy byśmy wyznaczali podzbiór od początku, albo np. od końca jak byśmy iterowali to suma byłaby zawsze na minusie i optymalniej byłoby wyznaczyć tylko jeden podzbiór). Np dla tablicy {2,3,4,5,-6,7,8,-9,10} największa suma byłaby dla podzbiorów {2,3,4,5} i {10,-9,8,7}.
Wymyśliłem, że najlepiej byłoby gdyby zacząć sprawdzać elementy od początku i sprawdzać jaki mają znak. Jeżeli element byłby dodani, to byśmy po prostu dodali go do sumy i zapisałbym do jakiejś zmiennej indeks tego elementu. Jeżeli byłby ujemny, sprawdziłbym czy jakbym szukał dalej to nie znajdę gdzieś podzbioru gdzie suma (tego podzbioru, który zaczynałby się od ujemnej wartości) byłaby dodatnia. Jeżeli byłaby dodatnia, to dodałbym to do sumy całkowitej tą sumę i zmieniłbym indeks tamtego elementu na ten. Wykonałbym to od końca jeszcze raz, z tym że nie do początku tylko do tego indeksu. Tylko problem pojawia się dla tablic typu: {2,-3,4}. Największa suma wynosiłaby 6, natomiast stosując ten algorytm dostałbym odpowiedź że tylko 3. Jak podejść do takiego problemu? Dużo łatwiej do rozwiązania byłby ten problem, gdyby można było zacząć od początku albo od końca tylko.
Ja bym zrobił dwie sumy "bieżące" i 2 maksymalne,od początku i od końca. W którejś z nich sprawdzał czy indeks nie jest zgodny z tym drugim, jak się "zejdą" to starczy dodać do siebie maksymalne i masz wynik.
A co zrobić jak się nie zejdą? Gdyby np pierwszy podzbior kończył się na indeksie i-1, a drugi na i+1. Indeks i-ty by miał ujemną wartość, mniejszą od sumy drugiego lub/i pierwszego podzbioru. Czyli byłoby prawdą, że suma(podzbior)+wartość(i)>0. Więc stosując mój czy twój algorytm, wyznaczylibysmy cały zbiór jako jeden podzbior, który nie byłby największy.
Wnile (indexpocz <= indexkon) i potem w tej pętli do początkowego dodajesz 1 a od końcowego odejmujesz, na pewno się zejdą (jak by tego nie zrobiły mógłbyś otrzymać zły wynik). Skoro dodajesz a nie mnożysz, to nie ma znaczenia czy np przy (3, 4, 5, 6) będą mieć po 2 elementy, czy też np początkowy 1 a końcowy 3. wynik będzie taki sam.
No tak, ale czy dla tablic typu (2,-4,-6,5,-6,7,8) (poprawny wynik 16, bo A={2} B={8,7,-6,5}) albo (2,-4,7,8) (poprawny wynik 17 A={2} B={8,7}) da to poprawny wynik? Albo (5,9,-8,10,-5,1) (poprawny wynik 20. A={5,9} B={1,-5,10})
Głównie chodzi mi o to, że:
- pierwszy zbiór będzie mniejszy, lub zbiory nie będą równe
- suma zbirów nie da całkowitego zbioru
- (ostatni przykład) potencjalnie lepiej wybrać większą liczbę na minusie (-8) bo przed nią stoi np 9 niż -5 bo przed nią stoi mniejsza liczba, ale tak na prawdę ta druga opcja będzie lepsza?
Też myślałem o takim algorytmie, ale nie podobało mi się to w tym.
Hm to może tak idziesz od początku i szukasz miejsca gdzie suma ma największą wartość, a potem od końca, ale do tego maksa + jedna pozycja. Potem można dla pewności zrobić odwrotnie, i sprawdzić jak wyjdzie ci większy wynik.
Nie jestem pewien, czy by to zadziałało.
Najprostszy przykład: {2,-3,4}. Idąc od początku, dostalibyśmy max sumę 3, wtedy i+1 pozycja byłaby równa 3, więc nie odbyłoby się poszukiwanie podzbioru "idąc" od końca. W celu sprawdzenia - Idąc od końca - również byśmy dostali taką samą wartość i taką samą sytuację. Ale jak prosto zauważyć, max byłby 6.
Na upartego, można byłoby rozważyć wszystkie sytuacje, tylko mało optymalne by coś takiego było. Bo dla np 4 elementowej {a,b,c,d} byłoby dość sporo możliwości: a, a+b, a+b+c, a+b+c+d, d, d+c, d+c+b, a+b+d, a+b+d+c (nie wiem czy wszystkie wymieniłem). Potem tylko to sumować i sprawdzać z jakąś inną zmienną czy będzie to większe i wyznaczyć tak max sumę.
Ale i - 1 była by jeszcze brana pod uwagę, więc poprawny wynik czyli 6 dla podciągów 2 i 4