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

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

მაგალითი

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

• 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.

ამოხსნა

ამოცანის ამოხსნის ყველაზე ტრივიალური გზაა ყველა ქვემიმდევრობის გენერირება და შესაბამისად მათი შემოწმება. ეს ამოხსნა არაეფექტურია, რადგან ის მუშაობს ექსპონენციალურ $O(2^{n})$ დროში.

ამოცანის ყველაზე გავრცელებული ალგორითმია $O(n^{2})$-დროში ამოხსნა, რომელიც დინამიური პროგრამირებას უკავშირდება. ეს ალგორითმი განიხილავს სიმრავლის პრეფიქსებს. ფორმალურად 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.