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

Στην επιστήμη των υπολογιστών το πρόβλημα μέγιστου αθροίσματος υποακολουθίας (Αγγλικά: Maximum 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 ;
}

The algorithm can also be easily modified to keep track of the starting and ending indices of the maximum subarray (see commented code).

Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem, the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of dynamic programming.

The runtime complexity of Kadane's algorithm is ${\mathcal {O}}(n)$.

Διαιρώ και βασιλεύω

Ένα αλγόριθμος Διαιρώ και Βασιλεύω παρουσιάστηκε από τον Jon Bentley του 1984 με πολυπλοκότητα ${\mathcal {O}}(n\log n)$.