Πρόβλημα μέγιστου υποσυστοιχίας στη C++

Το μέγιστο πρόβλημα υποσυστοιχίας είναι το ίδιο με το πρόβλημα μέγιστου τεμαχίου. Αυτό το σεμινάριο εξετάζει το πρόβλημα με την κωδικοποίηση σε C++. Το ερώτημα είναι: ποιο είναι το μέγιστο άθροισμα οποιασδήποτε πιθανής ακολουθίας διαδοχικών αριθμών μέσα σε έναν πίνακα; Αυτό μπορεί να σημαίνει ολόκληρο τον πίνακα. Αυτό το πρόβλημα και η επίλυσή του σε οποιαδήποτε γλώσσα, αναφέρεται ως Πρόβλημα Μέγιστου Υπο-Πίνακα. Ο πίνακας μπορεί να έχει πιθανούς αρνητικούς αριθμούς.

Η λύση πρέπει να είναι αποτελεσματική. Πρέπει να έχει την ταχύτερη χρονική πολυπλοκότητα. Προς το παρόν, ο ταχύτερος αλγόριθμος για τη λύση είναι γνωστός στην επιστημονική κοινότητα ως Kadane’s Algorithm. Αυτό το άρθρο εξηγεί τον αλγόριθμο του Kadane με τη C++.

Παραδείγματα Δεδομένων

Εξετάστε το ακόλουθο διάνυσμα (πίνακας):

Η φέτα (υπο-πίνακας) με το μέγιστο άθροισμα είναι η ακολουθία, {3, 5, -2, 4}, η οποία δίνει άθροισμα 10. Καμία άλλη πιθανή ακολουθία, ακόμη και ολόκληρος ο πίνακας, δεν θα δώσει άθροισμα έως η τιμή του 10. Ολόκληρος ο πίνακας δίνει ένα άθροισμα 7, το οποίο δεν είναι το μέγιστο άθροισμα.

Σκεφτείτε το ακόλουθο διάνυσμα:

Το τεμάχιο (υπο-πίνακας) με το μέγιστο άθροισμα είναι η ακολουθία, {4, −1, 2, 1} που δίνει άθροισμα 6. Σημειώστε ότι μπορεί να υπάρχουν αρνητικοί αριθμοί μέσα στον υποπίνακα για μέγιστο άθροισμα.

Σκεφτείτε το ακόλουθο διάνυσμα:

Το slice (υποπίνακας) με το μέγιστο άθροισμα είναι η ακολουθία, {3, 2} που δίνει άθροισμα 5.

Σκεφτείτε το ακόλουθο διάνυσμα:

Ο υποπίνακας με το μέγιστο άθροισμα είναι η ακολουθία, {3, 2, 6, -1, 4, 5, -1, 2} που δίνει άθροισμα 20. Είναι ολόκληρος ο πίνακας.

Σκεφτείτε το ακόλουθο διάνυσμα:

Υπάρχουν δύο υπο-πίνακες με μέγιστα αθροίσματα, εδώ. Το μεγαλύτερο άθροισμα είναι αυτό που θεωρείται ως λύση (απάντηση) για το μέγιστο πρόβλημα του υποπίνακα. Οι δευτερεύοντες πίνακες είναι: {5, 7} με άθροισμα 12 και {6, 5, 10, -5, 15, 4} με άθροισμα 35. Φυσικά, η φέτα με άθροισμα 35 είναι η απάντηση.

Σκεφτείτε το ακόλουθο διάνυσμα:

Υπάρχουν δύο υποπίνακες με μέγιστα αθροίσματα. Το μεγαλύτερο άθροισμα είναι αυτό που θεωρείται ως λύση για το μέγιστο πρόβλημα υπο-πίνακα. Οι δευτερεύοντες πίνακες είναι: {10, 15, 9} με άθροισμα 34 και {4, 6, 3, 2, 8, 3} με άθροισμα 26. Φυσικά, η φέτα με άθροισμα 34 είναι η απάντηση γιατί το πρόβλημα είναι να αναζητήσετε τον υποπίνακα με το μεγαλύτερο άθροισμα και όχι τον υποπίνακα με το μεγαλύτερο άθροισμα.

Ανάπτυξη του αλγόριθμου του Kadane

Οι πληροφορίες σε αυτήν την ενότητα του σεμιναρίου δεν είναι το πρωτότυπο έργο του Kadane. Είναι ο τρόπος του ίδιου του συγγραφέα να διδάξει τον αλγόριθμο του Kadane. Ένα από τα παραπάνω διανύσματα, με τα τρέχοντα σύνολα, είναι σε αυτόν τον πίνακα:

Το τρέχον σύνολο για έναν δείκτη είναι το άθροισμα όλων των προηγούμενων τιμών, συμπεριλαμβανομένης της τιμής του δείκτη. Υπάρχουν δύο ακολουθίες με μέγιστα αθροίσματα εδώ. Είναι {5, 7}, που δίνει άθροισμα 12, και {6, 5, 10, -5, 15, 4}, που δίνει άθροισμα 35. Η ακολουθία που δίνει άθροισμα 35 είναι η επιθυμητή .

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

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

Ένα άλλο διάνυσμα από πάνω, με τα τρέχοντα σύνολά του, είναι σε αυτόν τον πίνακα:

Υπάρχουν δύο ακολουθίες με μέγιστα αθροίσματα. Είναι {10, 15, 9}, που δίνει ένα άθροισμα 34. και {4, 6, 3, 2, 8, 3} που δίνει άθροισμα 26. Η ακολουθία που δίνει το άθροισμα 34, είναι η επιθυμητή.

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

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

Κωδικός από τον αλγόριθμο του Kadane σε C++

Ο κώδικας που δίνεται σε αυτήν την ενότητα του άρθρου δεν είναι απαραίτητα αυτός που χρησιμοποίησε ο Kadane. Ωστόσο, είναι από τον αλγόριθμό του. Το πρόγραμμα, όπως πολλά άλλα προγράμματα C++, θα ξεκινούσε με:

χρησιμοποιώντας namespace std?

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

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

Προσδιορίζεται το μέγεθος N του δεδομένου πίνακα (διάνυσμα). Η μεταβλητή, maxSum είναι ένα από τα πιθανά μέγιστα αθροίσματα. Ένας πίνακας έχει τουλάχιστον ένα μέγιστο άθροισμα. Η μεταβλητή runTotal αντιπροσωπεύει το τρέχον σύνολο σε κάθε ευρετήριο. Και οι δύο αρχικοποιούνται με την πρώτη τιμή του πίνακα. Σε αυτόν τον αλγόριθμο, εάν η επόμενη τιμή στον πίνακα είναι μεγαλύτερη από το τρέχον σύνολο, τότε αυτή η επόμενη τιμή θα γίνει το νέο τρέχον σύνολο.

Υπάρχει ένας κύριος βρόχος for. Η σάρωση ξεκινά από το 1 και όχι από το μηδέν λόγω της αρχικοποίησης των μεταβλητών, maxSum και runTotal σε A[0] που είναι το πρώτο στοιχείο του δεδομένου πίνακα.

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

Στη συνέχεια, υπάρχει μια κατασκευή if/else. Εάν η τρέχουσα τιμή από μόνη της είναι μεγαλύτερη από το τρέχον σύνολο μέχρι στιγμής, τότε αυτή η μεμονωμένη τιμή γίνεται το τρέχον σύνολο. Αυτό είναι βολικό ειδικά εάν όλες οι τιμές στον δεδομένο πίνακα είναι αρνητικές. Σε αυτήν την περίπτωση, η υψηλότερη αρνητική τιμή από μόνη της θα γίνει η μέγιστη τιμή (η απάντηση). Εάν η τρέχουσα τιμή από μόνη της δεν είναι μεγαλύτερη από το προσωρινό τρέχον σύνολο μέχρι στιγμής, τότε το τρέχον σύνολο γίνεται το προηγούμενο τρέχον σύνολο συν την τρέχουσα τιμή, - αυτό είναι το άλλο μέρος της κατασκευής if/else.

Το τελευταίο τμήμα κώδικα στον βρόχο for επιλέγει μεταξύ οποιουδήποτε προηγούμενου μέγιστου αθροίσματος για μια προηγούμενη ακολουθία (υποπίνακας) και οποιουδήποτε τρέχοντος μέγιστου αθροίσματος για μια τρέχουσα ακολουθία. Επομένως επιλέγεται η υψηλότερη τιμή. Μπορεί να υπάρχουν περισσότερα από ένα μέγιστο άθροισμα υποπίνακα. Σημειώστε ότι το τρέχον σύνολο θα ανέβαινε και θα έπεφτε, καθώς ο πίνακας σαρώνεται από αριστερά προς τα δεξιά. Πέφτει καθώς συναντά αρνητικές τιμές.

Το τελικό επιλεγμένο μέγιστο άθροισμα υπο-πίνακα επιστρέφεται μετά τον βρόχο for.

Το περιεχόμενο για μια κατάλληλη κύρια συνάρτηση C++, για τη συνάρτηση αλγορίθμου Kadane είναι:

Με αυτό, η έξοδος θα είναι:

10

6

5

είκοσι

35

3. 4

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

συμπέρασμα

Η χρονική πολυπλοκότητα για τον αλγόριθμο του Kadane είναι O(n), όπου n είναι ο αριθμός των στοιχείων στον δεδομένο πίνακα. Αυτή η χρονική πολυπλοκότητα είναι η ταχύτερη για το μέγιστο πρόβλημα υπο-πίνακα. Υπάρχουν άλλοι αλγόριθμοι που είναι πιο αργοί. Η ιδέα του αλγορίθμου του Kadane είναι να κάνει το τρέχον σύνολο, ενώ συγκρίνει τα μέγιστα αθροίσματα όπως αυτά συναντώνται, μετακινώντας από αριστερά προς τα δεξιά στον δεδομένο πίνακα. Εάν η τρέχουσα τιμή από μόνη της είναι μεγαλύτερη από το τρέχον σύνολο μέχρι στιγμής, τότε αυτή η μεμονωμένη τιμή γίνεται το νέο τρέχον σύνολο. Διαφορετικά, το νέο τρέχον σύνολο είναι το προηγούμενο τρέχον σύνολο συν το τρέχον στοιχείο, όπως αναμενόταν, καθώς σαρώνεται ο δεδομένος πίνακας.

Μπορεί να υπάρχουν περισσότερα από ένα μέγιστο άθροισμα, για διαφορετικούς πιθανούς υποπίνακες. Επιλέγεται το υψηλότερο μέγιστο άθροισμα, για όλους τους πιθανούς υποπίνακες.

Ποιοι είναι οι περιοριστικοί δείκτες για το εύρος του επιλεγμένου μέγιστου αθροίσματος; – Αυτό είναι συζήτηση για άλλη φορά!

Χρυσ