|
Στην [[πληροφορική]], το '''πρόβλημα μέγιστου αθροίσματος υποακολουθίας''' ([[Αγγλικά]]: ''Maximummaximum sum subarray problem'') είναι ένα πρόβλημα όπου έχουμε μια σειρά (πίνακα) από αριθμούς (θετικούς και, αρνητικούς αριθμούςή μιαμηδενικούς) και ψάχνουμε τηντη συνεχή μεγαλύτερη υποσειρά (υποπίνακα) αριθμών όπουπου έχουμεδίνει το μεγαλύτερο άθροισμα των στοιχείων. Για παράδειγμα, στηνστη σειρά των αριθμών −2, 1, −3, 4, −1, 2, 1, −5, 4 η υποσειρά αριθμών με το μέγιστο άθροισμα είναι η 4, −1, 2, 1, με άθροισμα 6. <ref> {{citation | first1 = Gerth Stølting | last1 = Brodal | first2 = Allan Grønlund | last2 = Jørgensen | contribution = A linear time algorithm for the ''k'' maximal sums problem | title = Mathematical Foundations of Computer Science 2007 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | volume = 4708 | year = 2007 | pages = 442–453 | doi = 10.1007/978-3-540-74456-6_40}} </ref> <ref>{{citation | first = T. | last = Takaoka | title = Efficient algorithms for the maximum subarray problem by distance matrix multiplication | journal = Electronic Notes in Theoretical Computer Science | volume = 61 | year = 2002 | url = http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf | accessdate = 2014-06-05 | archiveurl = https://web.archive.org/web/20131029172313/http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf | archivedate = 2013-10-29 | url-status = dead }}</ref>
== Εφαρμογές ==
Το πρόβλημα μέγιστου αθροίσματος υποακολουθίας έχει πρακτικές εφαρμογές στη [[Βιοπληροφορική]] για την ανάλυση γονιδιακών αλληλουχιών και στην [[μηχανική όραση]] για την ανίχνευση των πιο φωτεινών σημείων σε μια [[ψηφιογραφική εικόνα]].
== Αλγόριθμος Kadane ==
Σύμφωνα με τον αλγόριθμο του Kadane σαρώνουμε τις τιμές του πίνακα, και κάθε φορά υπολογίζουμε τηντη θέση με το μέγιστο θετικό άθροισμα της υποσειράς που τερματίζεται στο συγκεκριμένο σημείο. Η υποσειρά μπορεί να είναι άδεια (στην περίπτωση που το άθροισμα είναι μηδέν) ή να περιέχει περισσότερους από έναέναν αριθμούς από την προηγούμενη κατάσταση. <ref>{{cite web|last=Κλεάνθους Λοίζου|first=Στέλλα|title=1 ΕΠΛ 231 – Δομές Δεδομένων και Αλγόριθμοι Εργαστήριο 03: Πίνακες / Συλλογές Μέγιστο Άθροισμα Υπο‐ακολουθίας|url=https://www.cs.ucy.ac.cy/courses/EPL231/labs/2014S.EPL231.lab.03.arrays.pdf|work=ΕΠΛ 231 : Δομές Δεδομένων και Αλγόριθμοι|publisher=Τμήμα Πληροφορικής Πανεπιστήμιου Κύπρου|accessdate=5 Ιουνίου 2014|archiveurl=https://web.archive.org/web/20150420172749/https://www.cs.ucy.ac.cy/courses/EPL231/labs/2014S.EPL231.lab.03.arrays.pdf|archivedate=2015-04-20|url-status=dead}}</ref> ΣτηνΣτη γλώσσα [[Python]] η υλοποίηση του αλγορίθμου είναι:
<syntaxhighlight lang="python">
</syntaxhighlight>
Μια τροποποίηση του προβλήματος επιτρέπει την επιστροφή υποσειρών μηδενικού μεγέθους υποσειρών στις περιπτώσεις που ολόκληρος ο πίνακας περιέχει αρνητικούς αριθμούς και φαίνεται στο παρακάτω κώδικα:
<syntaxhighlight lang="python">
</syntaxhighlight>
Παρακάτω βρίσκεται η υλοποίηση σε [[C++]] όπου μπορεί να επιστρέψει (βρίσκονται σχολιασμένα) και τουτους δείκτες αρχής και τέλος της υποσειράς:
<syntaxhighlight lang="cpp">
int sequence(std::vector<int> const & numbers) {
// Αρχικοποίηση μεταβλητών
int max_so_far = numbers[0], max_ending_here = numbers[0];
// ΠΡΟΑΙΡΕΤΙΚΟ: Αυτές οι μεταβλητές μπορούν να χρησιμοποιηθούν για να έχουμε τους δείκτες αρχής και τέλους της υποσειράς
// υπολογισμός max_so_far
if(max_ending_here >= max_so_far ) {
max_so_far = max_ending_here;
// begin = begin_temp;
Ο αλγόριθμος μπορεί εύκολα να τροποποιηθεί και να αποθηκεύει τα σημεία της υποσειράς η οποία έχει μέγιστο άθροισμα (δείτε σχολιασμένο κώδικα). Η πολυπλοκότητα του αλγόριθμου Kadane είναι <math>\mathcal{O}(n)</math>.
== ΔιαιρώΔιαίρει και βασιλεύωβασίλευε ==
ΈναΈνας αλγόριθμος ''Διαιρώπου καιεπιλύει το πρόβλημα αυτό με χρήση της μεθόδου Βασιλεύω''[[Διαίρει οκαι οποίοςβασίλευε λύνει(υπολογιστές)|Διαίρει τοκαι πρόβλημα αυτόβασίλευε]]'', παρουσιάστηκε από τον Jon Bentley του 1984 με πολυπλοκότητα <math>\mathcal{O}(n \log n)</math>. <ref> {{citation | first = Jon | last = Bentley | title = Programming pearls: algorithm design techniques | journal = Communications of the ACM | volume = 27 | issue = 9 | year = 1984 | doi = 10.1145/358234.381162 | pages = 865–873}} </ref>
Παρακάτω δίνεται ο κώδικας σε pythonPython ώστε να ελέγχει εάν είναι κενός ο πίνακας ή αν όλοι οι αριθμοί είναι αρνητικοί και να επιστέφει τηντη μέγιστη τιμή καθώς και την αρχή και το τέλος του υποπίνακα.
<syntaxhighlight lang="python" line="1">
def max_subarray_Onlogn(arr,begin=-1,last=-1):
if begin==-1:
#αν δεν έχει δοθεί όριο βάζουμε όλο τον πίνακα
begin=0
last=len(arr)-1
| 