Acum, pentru a afla subsecvenţa de sumă maximă a subsecvenţei $a[x..y]$ studiem cele două cazuri posibile:

1. Dacă elementele de indice $x$ şi $y$ aparţin aceleiaşi subsecvenţe, atunci putem găsi ceea ce căutăm folosind algoritmul liniar direct pe şirul $a[x..y]$. Complexitate: $O(N / K)$.

# Dacă elementele de indice $x$ şi $y$ aparţin aceleiaşi subsecvenţe, atunci putem găsi ceea ce căutăm folosind algoritmul liniar direct pe şirul $a[x..y]$. Complexitate: $O(N / K)$.

2. Dacă nu sunt în aceeaşi secvenţă, atunci vom împărţi şirul $a[x..y]$ în:

# Dacă nu sunt în aceeaşi secvenţă, atunci vom împărţi şirul $a[x..y]$ în:

* un prefix de subsecvenţă din cele ce aparţin partiţionării,