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

Στην πληροφορική το πρόβλημα μέγιστου αθροίσματος υποακολουθίας (Αγγλικά: 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 ;}
Ο αλγόριθμος μπορεί εύκολα να τροποποιηθεί και να αποθηκεύει τα σημεία της υποσειράς η οποία έχει μέγιστο άθροισμα (δείτε σχολιασμένο κώδικα). Η πολυπλοκότητα του αλγόριθμου Kadane είναι .

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

Ένα αλγόριθμος Διαιρώ και Βασιλεύω ο οποίος λύνει το πρόβλημα αυτό παρουσιάστηκε από τον Jon Bentley του 1984 με πολυπλοκότητα . 
Παρακάτω δίνεται ο κώδικας σε python ώστε να ελέγχει εάν είναι κενός ο πίνακας ή αν όλοι είναι αρνητικοί και να επιστέφει την μέγιστη τιμή και την αρχή και το τέλος του υποπίνακα
 1 def max_subarray_Onlogn(arr,begin=-1,last=-1): 2     if begin==-1: 3         #αν δεν έχει δοθεί  όριο βάζουμε όλο τον πίνακα 4         begin=0 5         last=len(arr)-1 6     if begin>last: 7         return (0,-1,0) 8     elif begin==last: 9         return [arr[begin],begin,begin]10     median= int((begin+last)/2)11     lmax=sumx=arr[median]12     start=median13     for i in range(median-1,begin-1,-1):14         sumx+=arr[i]15         if sumx>lmax:16             lmax=sumx17             start=i18 19     rmax=sumx=arr[median+1]20     end=median+121     for i in range(median+2,last+1,+1):22         sumx+=arr[i]23         if sumx>rmax:24             rmax=sumx25             end=i26     k=max_subarray_Onlogn(arr,begin,median)27     if k[0]<lmax+rmax:28         k=(lmax+rmax,start,end)29     j=max_subarray_Onlogn(arr,median+1,last)30     if k[0]<j[0]or k[1]==-1:31         return j32     return k