To zadanie faktycznie jest złożone i liczenie wszystkich przypadków nie ma sensu. Mamy jednak tutaj pewne ograniczenie górne, które eliminuje nam pewne rozwiązania bez potrzeby ich dalszego badania i tracenia zasobów obliczeniowych.
TEORIA
Punktem wyjścia niech będzie definicja nowego ciągu utworzonego z ciągu pierwotnego. Każdy N-elementowy ciąg K możemy przekształcić do nowego ciągu Q :
K = {k1, k2, ... , kN}, N <= 50
Q = {q0, q1, ... , qM}, M <= N
Ciąg Q ma tę własność, że jest nierosnący i może być złożony z dowolnej kombinacji sum cyfr z ciągu K, przykładowo zakładając N=9 możemy skonstruować ciąg:
q0 = k8 + k9
q1 = k7
q2 = k6 + k5
q3 = k4 + k3 + k2 + k1
wtedy i tylko, gdy:
q3 <= q2 <= q1 <= q0
Na przykład wiemy, że każdy ciąg K będzie zawierał podciąg zupełny, który po przekształceniu do ciągu Q da nam ciąg jednoelementowy:
K = {1,2,6,3,4}
Q = {16}, bo q0 = 1 + 2 + 6 + 3 + 4
Z założeń zadania wiemy, że ostatni wyraz dowolnego podciągu ma osiągać maksimum. Taki wyraz możemy wyznaczyć, czyli wyznaczyć ostatnie j cyfr, które będą stanowić q0. Niestety jest to zadanie wieloetapowe, ponieważ zależy ono od pozostałych wyrazów ciągu Q, idąc od końca do początku ciągu K .
WYZNACZENIE ELEMENTU q0
Najpierw wędrujemy od końca ciągu K ku jego początkowi, szukając lokalnego maksimum. Jeśli na ostatniej N-tej pozycji mamy cyfrę taką że:
k(N-1) <= k(N)
to zakładamy, że jest to lokalne maksimum i przechodzimy do badania elementu q1. Jeśli tak nie jest, to sumujemy elementy i porównujemy ich sumę. Załóżmy, że lokalne maksimum jest na pozycji N-3. Wtedy zajdzie:
k(N-3) > k(N-2) + k(N-1) + k(N)
Przykładem niech będzie ciąg 12457321. Widzimy, że jego podział będzie zawsze taki, że ostatnie cztery cyfry będą razem 7321. Nie da się tego już podzielić, bo 7 zawsze będzie większa od sumy 3, 2 i 1. Dla tego ciągu q0 = 13. To jednak nie jest odpowiedź, bo q0 może być większe, a to wszystko zależy od tego, czy pozostałe elementy spełnią założenie relacji <=.
POZOSTAŁE ELEMENTY CIĄGU Q
Z poprzedniego kroku mamy już pewne górne ograniczenie. Otóż element q1 musi być mniejszy bądź równy q0. Najrozsądniej będzie dokładać kolejne cyfry tworząc sumy q1 dopóki warunek q0 => q1 będzie spełniony. Gdy przekroczymy tę barierę, to wyznaczyliśmy q1. Teraz należy analogicznie wyznaczyć q2 i pozostałe elementy, dochodząc do początku ciągu. Oczywiście może się zdarzyć, że q1 < q2 nawet jeśli q2 składa się z jednego elementu. Przykład 13281237321. W tym przypadku:
q0 = 13 = 7 + 3 + 2 + 1
q1 = 6 = 1 + 2 + 3
q2 = 8
Widzimy więc, że nie ma sensu badanie ciągów, dla których q0 = 7 + 3 + 2 + 1. Innymi słowy z sekwencji 12457321 nie da się zbudować pociągu, który miałby ostatni wyraz równy 7321, oszczędzamy więc czas. Co wtedy? Wtedy należy wrócić do q0 i powiększyć je o dodatkową cyfrę i powtórzyć całą procedurę, czyli wracając do przykładu wyżej teraz q0 będzie równe 5+7+3+2+1=18.
CIĄG Q SPEŁNIA ZAŁOŻENIA
Postępując z powyższą instrukcją w końcu dojdziemy do sytuacji, kiedy to:
qM <= ... <= q1 <= q0
Niestety to nie koniec. Po pierwsze wyznaczyliśmy tylko q0 graniczne. Dokładając kolejną liczbę z lewej strony otrzymamy nowe q0 i w rzeczywistości tak musimy zrobić, bo mamy zbadać przecież wszystkie podciągi. Zwróćmy uwagę, że dokładając cyfry z lewej strony w końcu dojdziemy do sytuacji, gdzie podciąg będzie równy wyjściowemu ciągowi K. Po drugie, co gorsze, musimy również zbadać pozostałe przypadki zmniejszając i-ty wyraz qi. Niemniej, procedury zawsze zostaną przerwane, jeśli zajdzie:
q'(i+1) > q'(i)
i dalsze badanie wyrazów nie ma sensu.