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

მასალა ვიკიპედიიდან — თავისუფალი ენციკლოპედია
ნავიგაციაზე გადასვლა ძიებაზე გადასვლა

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

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

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

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

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

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

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