Πρόβλημα μέγιστου αθροίσματος υποακολουθίας

Στην πληροφορική, το πρόβλημα μέγιστου αθροίσματος υποακολουθίας (Αγγλικά: maximum sum subarray problem) είναι ένα πρόβλημα όπου έχουμε μια σειρά (πίνακα) από αριθμούς (θετικούς, αρνητικούς ή μηδενικούς) και ψάχνουμε τη συνεχή υποσειρά (υποπίνακα) αριθμών που δίνει το μεγαλύτερο άθροισμα. Για παράδειγμα, στη σειρά των αριθμών −2, 1, −3, 4, −1, 2, 1, −5, 4 η υποσειρά αριθμών με το μέγιστο άθροισμα είναι η 4, −1, 2, 1, με άθροισμα 6.

Εφαρμογές

Το πρόβλημα μέγιστου αθροίσματος υποακολουθίας έχει πρακτικές εφαρμογές στη Βιοπληροφορική για την ανάλυση γονιδιακών αλληλουχιών και στην μηχανική όραση για την ανίχνευση των πιο φωτεινών σημείων σε μια ψηφιογραφική εικόνα.

Αλγόριθμος Kadane

Σύμφωνα με τον αλγόριθμο του Kadane σαρώνουμε τις τιμές του πίνακα, και κάθε φορά υπολογίζουμε τη θέση με το μέγιστο θετικό άθροισμα της υποσειράς που τερματίζεται στο συγκεκριμένο σημείο. Η υποσειρά μπορεί να είναι άδεια (στην περίπτωση που το άθροισμα είναι μηδέν) ή να περιέχει περισσότερους από έναν αριθμούς από την προηγούμενη κατάσταση. Στη γλώσσα Python η υλοποίηση του αλγορίθμου είναι:

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Μια τροποποίηση του προβλήματος επιτρέπει την επιστροφή υποσειρών μηδενικού μεγέθους στις περιπτώσεις που ολόκληρος ο πίνακας περιέχει αρνητικούς αριθμούς και φαίνεται στο παρακάτω κώδικα:

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Παρακάτω βρίσκεται η υλοποίηση σε C++ όπου μπορεί να επιστρέψει (βρίσκονται σχολιασμένα) και τους δείκτες αρχής και τέλος της υποσειράς:

int sequence(std::vector<int> const & numbers) {
        // Αρχικοποίηση μεταβλητών
        int max_so_far = numbers[0], max_ending_here = numbers[0];

        // ΠΡΟΑΙΡΕΤΙΚΟ: Αυτές οι μεταβλητές μπορούν να χρησιμοποιηθούν για να έχουμε τους δείκτες αρχής και τέλους της υποσειράς
        // size_t begin = 0;
        // size_t begin_temp = 0;
        // size_t end = 0;

        // Βρες την υποσειρά κάνοντας επανάληψη μέχρι το τέλος του πίνακα
        for(size_t i = 1; i < numbers.size(); i++) {
                // υπολογισμός max_ending_here
                if(max_ending_here < 0) {
                        max_ending_here = numbers[i];
                        
                        // begin_temp = i;
                }
                else {
                        max_ending_here += numbers[i];
                }

                // υπολογισμός max_so_far
                if(max_ending_here >= max_so_far ) {
                        max_so_far = max_ending_here;
                        
                        // begin = begin_temp;
                        // end = i;
                }
        }
        return max_so_far ;
}

Ο αλγόριθμος μπορεί εύκολα να τροποποιηθεί και να αποθηκεύει τα σημεία της υποσειράς η οποία έχει μέγιστο άθροισμα (δείτε σχολιασμένο κώδικα). Η πολυπλοκότητα του αλγόριθμου Kadane είναι ${\mathcal {O}}(n)$.

Διαίρει και βασίλευε

Ένας αλγόριθμος που επιλύει το πρόβλημα αυτό με χρήση της μεθόδου Διαίρει και βασίλευε, παρουσιάστηκε από τον Jon Bentley του 1984 με πολυπλοκότητα ${\mathcal {O}}(n\log n)$. Παρακάτω δίνεται ο κώδικας σε Python ώστε να ελέγχει εάν είναι κενός ο πίνακας ή αν όλοι οι αριθμοί είναι αρνητικοί και να επιστέφει τη μέγιστη τιμή καθώς και την αρχή και το τέλος του υποπίνακα.

def max_subarray_Onlogn(arr,begin=-1,last=-1):
    if begin==-1:
        #αν δεν έχει δοθεί όριο βάζουμε όλο τον πίνακα
        begin=0
        last=len(arr)-1
    if begin>last:
        return (0,-1,0)
    elif begin==last:
        return [arr[begin],begin,begin]
    median= int((begin+last)/2)
    lmax=sumx=arr[median]
    start=median
    for i in range(median-1,begin-1,-1):
        sumx+=arr[i]
        if sumx>lmax:
            lmax=sumx
            start=i

    rmax=sumx=arr[median+1]
    end=median+1
    for i in range(median+2,last+1,+1):
        sumx+=arr[i]
        if sumx>rmax:
            rmax=sumx
            end=i
    k=max_subarray_Onlogn(arr,begin,median)
    if k[0]<lmax+rmax:
        k=(lmax+rmax,start,end)
    j=max_subarray_Onlogn(arr,median+1,last)
    if k[0]<j[0]or k[1]==-1:
        return j
    return k