უდიდესი ქვემიმდევრობის ამოცანა
კომპიუტერულ მეცნიერებაში, უდიდესი ქვემიმდევრობის ამოცანა გულისხმობს მიმდევრობის მოსაზღვრე ელემენტებისგან შედგენილ ქვესიმრავლეებს შორის უდიდესი ჯამის მქონე ქვესიმრავლის პოვნას. ფორმალურად, ვიპოვოთ ისეთი i {\displaystyle i} და j {\displaystyle j} ინდექსები, რომ 1 ≤ i ≤ j ≤ n {\displaystyle 1\leq i\leq j\leq n} , და ჯამი: ∑ x = i j A [ x ] {\displaystyle \sum _{x=i}^{j}A[x]} რაც შეიძლება დიდია. მაგალითად, ამ მოცემული სიმრავლისთვის [ − 2 , 1 , − 3 , 4 , − 1 , 2 , 1 , − 5 , 4 ] {\displaystyle [-2,1,-3,4,-1,2,1,-5,4]} უდიდესი ჯამის მქონე ქვემიმდევრობაა [ 4 , − 1 , 2 , 1 ] {\displaystyle [4,-1,2,1]} ჯამით 6 {\displaystyle 6} . ამოცანა ტრივიალურია როდესაც: მასივი შეიცავს ყველა არა-უარყოფით რიცხვს. მაქსიმალური ქვემიმდევრობა მთლიანად მიმდევრობაა. მასივი შეიცავს ყველა არა-დადებით რიცხვს, მაშინ მაქსიმალური ქვემიმდევრობაა რიცხვი უმცირესი მოდულით. ამოცანა რამდენიმე განსხვავებული ალგორითმით იხსნება, თუმცა მათ შორის ყველაზე ეფექტურია კადეინის ალგორითმი, რომელიც ამოცანას O ( n ) {\displaystyle O(n)} -დროში ხსნის.