Αλγόριθμος 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} = 11, είναι το μέγιστο άθροισμα σε όλους τους πιθανούς συνδυασμούς του υποπίνακα του παραπάνω πίνακα. Άρα, για τον παραπάνω πίνακα, ο μέγιστος υποπίνακας είναι {5,1,6}.

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

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

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

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

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

Βήμα 1) Αρχικοποιήστε το max_sum με ελάχιστη ακέραια τιμή και εκχωρήστε τις μεταβλητές "begin" και "end" με μηδέν.

Βήμα 2) Έστω i και j ο δείκτης του πίνακα, όπου το "j" είναι μεγαλύτερο από ίσο με το "i". Αντιπροσωπεύει τον αρχικό δείκτη του υποσυστοιχίας και το "j" αντιπροσωπεύει τον τελικό δείκτη του υποσυστοιχίας.

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

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

Βήμα 5) Ελέγξτε εάν το "j" φτάνει στο τέλος του πίνακα ή όχι. Εάν το "j" φτάσει στο τέλος του πίνακα, τότε αυξήστε το "i" και αλλάξτε την τιμή current_sum σε 0.

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

Βήμα 7) Στο τέλος αυτών των δύο βρόχων, το max_sum θα έχει το μεγαλύτερο άθροισμα υποπίνακα.

Ψευδοκώδικας για απλή προσέγγιση

  function maximumSubarraySum():
    input: array
  for all possible subArray from array:
    calculate sum of each sub array
    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 λειτουργεί μόνο για θετικούς πίνακες αριθμών.

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

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

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

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

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

• Εάν το current_sum είναι μικρότερο από το τρέχον στοιχείο, τότε η τιμή current_sum θα είναι το τρέχον στοιχείο.
• Εάν το max_sum είναι μικρότερο από το current_sum, τότε το max_sum θα είναι current_sum.

Βήμα 3) Εκτελώντας το προηγούμενο βήμα για ολόκληρο τον πίνακα, θα έχουμε τον μεγαλύτερο συνεχόμενο υποπίνακα αθροίσματος στη μεταβλητή "max_sum".

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

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

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

Εδώ είναι τα βήματα του αλγόριθμου του Kadane:

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

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

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

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

Βήμα 4) Η επόμενη τιμή είναι 1. Εάν το προσθέσουμε με το τρέχον_άθροισμα, τότε το τρέχον_άθροισμα θα είναι 3. Ωστόσο, το μέγιστο_άθροισμα είναι μεγαλύτερο από το τρέχον_άθροισμα. Επομένως, το max_sum δεν θα ενημερωθεί.

Βήμα 5) Στον δείκτη 3, η τιμή είναι τρία. Θα ενημερώσουμε την τιμή αυξάνοντας το τρέχον_άθροισμα κατά 3. Άρα, το τρέχον_άθροισμα θα είναι 6.

Σε αυτήν την περίπτωση, το max_sum είναι μικρότερο από το current_sum. Έτσι, το max_sum θα ενημερωθεί με την τιμή του current_sum.

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

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

Ψευδοκώδικας για τον αλγόριθμο του Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each elements 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 -10000000
  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

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

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

Αν ένας πίνακας έχει σύνολο N στοιχεία, στη συνέχεια χρησιμοποιώντας δύο βρόχους, θα περάσουμε από το Ν² στοιχεία. Ως αποτέλεσμα, η χρονική πολυπλοκότητα για μια απλή προσέγγιση για την εύρεση του μεγαλύτερου αθροίσματος συνεχούς υποσυστοιχίας θα είναι O(N2). Εδώ, το "O" σημαίνει τη συνάρτηση πολυπλοκότητας.

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

Ως αποτέλεσμα, εάν ο πίνακας εισόδου έχει μέγεθος N, τότε η χρονική πολυπλοκότητα του Αλγόριθμου του Kadane θα είναι O(N). Αυτό είναι πιο γρήγορο από την απλή προσέγγιση. Για παράδειγμα, ένας πίνακας που περιέχει 100 στοιχεία. Η απλή προσέγγιση θα πάρει χρόνο CPU 100*100 ή 10,000. Αλλά ο αλγόριθμος του Kadane θα πάρει μόνο 100 χρόνο CPU.