უგრძესი ზრდადი ქვემიმდევრობა

მასალა ვიკიპედიიდან — თავისუფალი ენციკლოპედია
Jump to navigation Jump to search

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

მაგალითი[რედაქტირება | წყაროს რედაქტირება]

მოცემულია მიმდევრობა:

  • 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

უგრძესი ზრდადი ქვემიმდევრობაა:

  • 0, 2, 6, 9, 11, 15.

მაგრამ ასევე გვაქვს სხვა მაგალითებიც:

  • 0, 4, 6, 9, 11, 15
  • 0, 2, 6, 9, 13, 15
  • 0, 4, 6, 9, 13, 15.

ამოხსნა[რედაქტირება | წყაროს რედაქტირება]

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

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

ამ ალგორითმის იმპლემენტაცია C++-ში, სადაც n აღნიშნავს მასივის სიგრძეს, mas აღნიშნავს მასივს, რომლის უგრძეს ზრდად ქვემიმდევრობას ვეძებთ, dp-მასივში i-ურ პოზიციაზე i-სიგრძის პრეფიქსის უგრძესი ზრდადი ქვემიმდევრობაა მოცემული. საბოლოოდ dp-მასივის უდიდესი ელემენტი წარმოადგენს მიმდევრობის უგრძესი ზრდადი ქვემიმდევრობის სიგრძეს.

    for(int i=0; i<n; i++){
        dp[i]=1;
        for(int j=0; j<i; j++){
            if(mas[j]<mas[i]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }


ლიტერატურა[რედაქტირება | წყაროს რედაქტირება]

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