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

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

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

 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.

კატეგორია:კომბინატორიკა
კატეგორია:ფორმალური ენები