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

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

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

მაგალითად ამ მოცემული სიმრავლისთვის  უდიდესი ჯამის მქონე ქვემიმდევრობაა  ჯამით .

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

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

კადეინის ალგორითმი 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.

კატეგორია:პროგრამირება
კატეგორია:ალგორითმები