უდიდესი ქვემიმდევრობის ამოცანა

კომპიუტერულ მეცნიერებაში, უდიდესი ქვემიმდევრობის ამოცანა გულისხმობს მიმდევრობის მოსაზღვრე ელემენტებისგან შედგენილ ქვესიმრავლეებს შორის უდიდესი ჯამის მქონე ქვესიმრავლის პოვნას. ფორმალურად, ვიპოვოთ ისეთი $i$ და $j$ ინდექსები, რომ $1\le i\le j\le n$, და ჯამი:

$\sum _{x=i}^{j}A[x]$

რაც შეიძლება დიდია.

მაგალითად, ამ მოცემული სიმრავლისთვის $[-2,1,-3,4,-1,2,1,-5,4]$ უდიდესი ჯამის მქონე ქვემიმდევრობაა $[4,-1,2,1]$ ჯამით $6$.

ამოცანა ტრივიალურია როდესაც:

1. მასივი შეიცავს ყველა არა-უარყოფით რიცხვს. მაქსიმალური ქვემიმდევრობა მთლიანად მიმდევრობაა.
2. მასივი შეიცავს ყველა არა-დადებით რიცხვს, მაშინ მაქსიმალური ქვემიმდევრობაა რიცხვი უმცირესი მოდულით.

ამოცანა რამდენიმე განსხვავებული ალგორითმით იხსნება, თუმცა მათ შორის ყველაზე ეფექტურია კადეინის ალგორითმი, რომელიც ამოცანას $O(n)$-დროში ხსნის.

კადეინის ალგორითმი C++-ზე

    //შევქმნათ ცვლადი, რომელიც შეინახავს ქვემიმდევრობის უდიდეს ჯამს
    // და ცვლადი რომელიც შეინახავს ჯამს
    int best = INT_MIN, sum = 0;
    //გადავარჩიოთ მასივის ყველა ელემენტი
    for (int i = 0; i < n; i++) {
        // ჯამი გაიზრდება, თუ i-ური ელემენტის მიმატებით ის გაიზრდება
        // თუ არა, ის i-ური ელემენტის ტოლი გახდება
        sum = max(array[i],sum+array[i]);
        // შედეგი გაიზრდება, თუ sum-ში მოცემულ მომენტში უდიდესი ჯამია
        best = max(best,sum);
    }
    cout << best << "\n";

ლიტერატურა

• Antti Laaksonen, Competitive Programmer's Handbook, p22.