Αλγόριθμος Kadence: Largest Sum Contiguous Subarray

Ποιο είναι το μεγαλύτερο άθροισμα συνεχόμενων υποπίνακων;

Ένας υποπίνακας είναι ένα συνεχές μέρος ενός πίνακα. Μπορεί να είναι ένα μεμονωμένο στοιχείο ενός πίνακα ή κάποιο κλάσμα του πίνακα. Ο συνεχής υποπίνακας μεγαλύτερου αθροίσματος σημαίνει υποσυστοιχία που έχει τη μέγιστη τιμή αθροίσματος.

Για παράδειγμα, πάρτε τον πίνακα {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Οι υποπίνακες του μπορούν να είναι {-10, 5, 1, 6}, {5, 1, 6} ή {2, -7, 3, -5}, και ούτω καθεξής. Ωστόσο, το {5, 1, 6, 3} δεν μπορεί να είναι υποπίνακας επειδή τα στοιχεία δεν βρίσκονται σε συνεχόμενη ακολουθία.

Αν παρατηρήσετε, μεταξύ όλων των υποπίνακων, ο επισημασμένος υποπίνακας {5, 1, 6} έχει τη μέγιστη τιμή αθροίσματος:

Το άθροισμα του υποπίνακα {5, 1, 6} είναι 12, το μέγιστο άθροισμα όλων των πιθανών υποπινάκων του παραπάνω πίνακα. Έτσι, για αυτόν τον πίνακα, το μέγιστο άθροισμα ενός συνεχόμενου υποπίνακα είναι {5, 1, 6}.

Απλή προσέγγιση για την επίλυση του μεγαλύτερου αθροίσματος συνεχόμενων υποπίνακα

Ο απλός τρόπος για να λύσετε αυτό το πρόβλημα είναι να χρησιμοποιήσετε δύο βρόχους για να βρείτε όλους τους υποπίνακες, να υπολογίσετε το άθροισμα και στη συνέχεια να βρείτε τη μέγιστη τιμή του.

Ακολουθεί το διάγραμμα ροής για την απλή προσέγγιση εύρεσης του μεγαλύτερου αθροίσματος συνεχόμενου υποπίνακα. Πρόκειται για μια προσέγγιση ωμής βίας, καθώς εξετάζουμε κάθε πιθανό υποπίνακα.

Εδώ είναι τα απλά βήματα για να το κάνετε αυτό.

Βήμα 1) αρχικοποίηση μέγιστο_άθροισμα με την ελάχιστη ακέραια τιμή και ορίστε αρχίζουν και τέλος στο μηδέν.

Βήμα 2) Ας i και j να είναι δείκτες πίνακα όπου j είναι μεγαλύτερο ή ίσο με i; i σηματοδοτεί την έναρξη του υποπίνακα και j το τέλος του.

Βήμα 3) τρέχον_άθροισμα περιέχει το τρέχον άθροισμα. Μετά από κάθε ενημέρωση, ελέγξτε αν τρέχον_άθροισμα είναι μεγαλύτερη από ό, τι μέγιστο_άθροισμα.

Βήμα 4) If τρέχον_άθροισμα είναι μεγαλύτερο, αντικαταστήστε μέγιστο_άθροισμα με αυτό.

Βήμα 5) Κατά τη j φτάνει στο τέλος του πίνακα, αυξάνεται i και επαναφορά τρέχον_άθροισμα να 0.

Βήμα 6) Επαναλάβετε μέχρι i φτάνει στο τέλος του πίνακα. μέγιστο_άθροισμα τότε περιέχει το μεγαλύτερο άθροισμα υποπίνακα.

Παρατσούκλι Code για Απλή Προσέγγιση

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ Εφαρμογή Απλής Προσέγγισης

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
    int max_sum = -1e9;
    int begin = 0;
    int end = 0;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += array[j];
            if (max_sum < current_sum) {
                max_sum = current_sum;
                begin = i;
                end = j;
            }
        }
    }
    cout << "largest sum is " << max_sum << endl;
    cout << "largest sum contiguous subarray: ";
    for (int i = begin; i <= end; i++) {
        cout << array[i] << "\t";
    }
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

Παραγωγή:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python Εφαρμογή Απλής Προσέγγισης

def maximumSubarraySum(numbers):
    max_sum, begin, end = -1e9, 0, 0
    for i in range(len(numbers)):
        current_sum = 0
        for j in range(i, len(numbers)):
            current_sum += numbers[j]
            if max_sum < current_sum:
                max_sum = current_sum
                begin, end = i, j
    print("largest sum is ", max_sum)
    print("largest sum contiguous subarray: ", end='')
    for i in range(begin, end + 1):
        print(numbers[i], end='\t')

numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5]
maximumSubarraySum(numbers)

Παραγωγή:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Αλγόριθμος Kadane για την εύρεση του μεγαλύτερου συνεχόμενου υποπίνακα αθροίσματος

Ο Αλγόριθμος Kadane είναι μια μέθοδος Δυναμικού Προγραμματισμού που χρησιμοποιεί έναν μόνο βρόχο αντί για δύο. Χειρίζεται πίνακες με μικτούς θετικούς και αρνητικούς αριθμούς, εφόσον τουλάχιστον μία τιμή δεν είναι αρνητική.

Χρειαζόμαστε μόνο δύο μεταβλητές για να βρούμε τον μεγαλύτερο συνεχόμενο υποπίνακα αθροίσματος. Ακολουθεί το διάγραμμα ροής:

Ακολουθούν τα βήματα για τον αλγόριθμο του Kadane:

Βήμα 1) Δημιουργήστε δύο μεταβλητές, τρέχον_άθροισμα και μέγιστο_άθροισμα.

τρέχον_άθροισμα διατηρεί το μέγιστο άθροισμα που τελειώνει σε έναν συγκεκριμένο δείκτη πίνακα, ενώ μέγιστο_άθροισμα αποθηκεύει τη μεγαλύτερη αθροιστική τιμή που έχει παρατηρηθεί μέχρι στιγμής.

Βήμα 2) Προσθέστε κάθε στοιχείο πίνακα σε τρέχον_άθροισμαΣτη συνέχεια, ελέγξτε τις δύο παρακάτω συνθήκες:

• If τρέχον_άθροισμα είναι μικρότερο από το τρέχον στοιχείο, τότε τρέχον_άθροισμα γίνεται το τρέχον στοιχείο.
• If μέγιστο_άθροισμα είναι λιγότερο από τρέχον_άθροισμα, Τότε μέγιστο_άθροισμα γίνεται τρέχον_άθροισμα.

Βήμα 3) Αφού επαναλάβετε το προηγούμενο βήμα για ολόκληρο τον πίνακα, μέγιστο_άθροισμα περιέχει τον μεγαλύτερο συνεχόμενο υποπίνακα αθροίσματος.

Παράδειγμα αλγόριθμου Kadane

Παρουσιάζουμε τον Αλγόριθμο του Kadane σε έναν μικρό πίνακα και εξετάζουμε κάθε βήμα της εύρεσης του μεγαλύτερου συνεχόμενου υποπίνακα αθροίσματος.

Ας υποθέσουμε ότι ο δοθέντας πίνακας είναι όπως ο ακόλουθος:

Ακολουθούν τα βήματα του αλγορίθμου Kadane:

Βήμα 1) Δημιουργήστε δύο μεταβλητές, τρέχον_άθροισμα και μέγιστο_άθροισμα. Αντιστοίχιση INT_MIN σε μέγιστο_άθροισμα και από το μηδέν έως τρέχον_άθροισμαΕδώ, το INT_MIN αντιπροσωπεύει την ελάχιστη ακέραια τιμή.

Βήμα 2) Στον δείκτη 0, η τιμή είναι 4. Έτσι, τρέχον_άθροισμα = 0 + 4 = 4. Εφόσον τρέχον_άθροισμα είναι μεγαλύτερο από μέγιστο_άθροισμα, μέγιστο_άθροισμα γίνεται 4.

Βήμα 3) Στον δείκτη 1, η τιμή είναι -2. Έτσι, τρέχον_άθροισμα = 4 + (-2) = 2.

Αυτή τη φορά τρέχον_άθροισμα είναι λιγότερο από μέγιστο_άθροισμαΩς αποτέλεσμα, η αξία του μέγιστο_άθροισμα δεν ενημερώνεται.

Βήμα 4) Η επόμενη τιμή είναι 1. Προσθέτοντάς την στο τρέχον_άθροισμα δίνει 3. Δεδομένου ότι μέγιστο_άθροισμα (4) είναι ακόμα μεγαλύτερο από τρέχον_άθροισμα, μέγιστο_άθροισμα δεν ενημερώνεται.

Βήμα 5) Στον δείκτη 3, η τιμή είναι 3. Αύξηση τρέχον_άθροισμα κατά 3 δίνει τρέχον_άθροισμα = 6.

Στην περίπτωση αυτή, μέγιστο_άθροισμα είναι μικρότερο από τρέχον_άθροισμα, Οπότε μέγιστο_άθροισμα ενημερώνεται με την τιμή του τρέχον_άθροισμα.

Βήμα 6) Για το τελευταίο στοιχείο του πίνακα, έχουμε -1. Προσθέτοντάς το στο τρέχον_άθροισμα δίνει 5, το οποίο είναι μικρότερο από μέγιστο_άθροισμα. Ετσι, μέγιστο_άθροισμα παραμένει 6.

Καθώς φτάσαμε στο τέλος του πίνακα, ο αλγόριθμος τελειώνει εδώ. Τώρα, μέγιστο_άθροισμα περιέχει το μέγιστο άθροισμα, το οποίο είναι 6. Ο υποπίνακας είναι {4, -2, 1, 3}.

Παρατσούκλι Code για τον Αλγόριθμο του Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++ Υλοποίηση του αλγορίθμου Kadane

#include <iostream>
using namespace std;
void kadane(int array[], int n) {
    int current_sum = 0;
    int max_sum = -1e9;
    // -1e9 means -1,000,000,000
    for (int i = 0; i < n; i++) {
        current_sum += array[i];
        if (max_sum < current_sum) {
            max_sum = current_sum;
        }
        if (current_sum < array[i]) {
            current_sum = array[i];
        }
    }
    cout << "largest sum is " << max_sum << endl;
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    kadane(array, sizeof(array) / sizeof(array[0]));
}

Παραγωγή:

largest sum is 12

Python Υλοποίηση του αλγορίθμου Kadane

def kadane(numbers):
    current_sum = 0
    max_sum = -1e9
    for i in range(len(numbers)):
        current_sum += numbers[i]
        if max_sum < current_sum:
            max_sum = current_sum
        if current_sum < numbers[i]:
            current_sum = numbers[i]
    print("largest sum is ", max_sum)

kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])

Παραγωγή:

largest sum is 12

Ανάλυση πολυπλοκότητας για το μεγαλύτερο συνεχόμενο υποσύστημα αθροίσματος

Η απλή προσέγγιση χρησιμοποιεί δύο βρόχους για να υπολογίσει κάθε πιθανό άθροισμα υποπίνακα και να εντοπίσει το μεγαλύτερο. Είναι μια προσέγγιση ωμής βίας· κάθε βρόχος εκτελείται μέχρι το τέλος του παράταξη, δίνοντας O(N²) χρόνο.

Ο αλγόριθμος του Kadane χρησιμοποιεί μόνο έναν βρόχο, δίνοντας χρόνο O(N) και επιπλέον χώρο O(1). Σε έναν πίνακα 100 στοιχείων, η απλή προσέγγιση εκτελεί 100 × 100 = 10,000 πράξεις, ενώ ο αλγόριθμος του Kadane εκτελεί μόνο 100 — μια δραματική επιτάχυνση για μεγάλες εισόδους.

Συχνές Ερωτήσεις