Kadanes Algorithmus ist ein dynamischer Programmieransatz zur Lösung des Problems des maximalen Subarrays, bei dem es darum geht, das zusammenhängende Subarray mit der maximalen Summe in einem Zahlenarray zu finden. Der Algorithmus wurde 1984 von Jay Kadane vorgeschlagen und hat eine Zeitkomplexität von O(n).
Geschichte des Kadane-Algorithmus:
Kadanes Algorithmus ist nach seinem Erfinder Jay Kadane benannt, einem Informatikprofessor an der Carnegie Mellon University. Er beschrieb den Algorithmus erstmals in einem Artikel mit dem Titel „Maximum Sum Subarray Problem“, der 1984 im Journal of the Association for Computing Machinery (ACM) veröffentlicht wurde.
Das Problem, das maximale Subarray zu finden, wird seit den 1970er Jahren von Informatikern untersucht. Es handelt sich um ein bekanntes Problem im Bereich des Algorithmusdesigns und der Algorithmenanalyse, das in einer Vielzahl von Bereichen Anwendung findet, darunter Signalverarbeitung, Finanzen und Bioinformatik.
Vor Kadanes Algorithmus wurden andere Algorithmen zur Lösung des Maximum-Subarray-Problems vorgeschlagen, beispielsweise der Brute-Force-Ansatz, der alle möglichen Subarrays überprüft, und der Divide-and-Conquer-Algorithmus. Allerdings weisen diese Algorithmen eine höhere Zeitkomplexität auf und sind weniger effizient als Kadanes Algorithmus.
Kadanes Algorithmus ist in der Informatik weit verbreitet und hat sich zu einem klassischen Beispiel dynamischer Programmierung entwickelt. Seine Einfachheit, Effizienz und Eleganz haben es zu einer beliebten Lösung für das Maximum-Subarray-Problem und zu einem wertvollen Werkzeug für das Design und die Analyse von Algorithmen gemacht.
Funktionsweise des Kadene-Algorithmus:
Der Algorithmus iteriert über das Array und verfolgt die maximale Summe des Subarrays, das an jeder Position endet. An jeder Position i haben wir zwei Möglichkeiten: entweder das Element an Position i zum aktuellen maximalen Subarray hinzufügen oder ein neues Subarray an Position i beginnen. Das Maximum dieser beiden Optionen ist das maximale Subarray, das an Position i endet.
Wir pflegen zwei Variablen, max_so_far und max_ending_here, um die bisher gesehene maximale Summe bzw. die maximale Summe, die an der aktuellen Position endet, zu verfolgen. Der Algorithmus beginnt damit, beide Variablen auf das erste Element des Arrays zu setzen. Dann durchlaufen wir das Array vom zweiten Element bis zum Ende.
An jeder Position i aktualisieren wir max_ending_here, indem wir das Maximum des aktuellen Elements nehmen und das aktuelle Element zum vorherigen maximalen Subarray hinzufügen. Anschließend aktualisieren wir max_so_far so, dass es das Maximum von max_so_far und max_ending_here ist.
bash schlafen
Der Algorithmus gibt max_so_far zurück, was die maximale Summe aller Unterarrays im Array ist.
Hier ist der Schritt-für-Schritt-Prozess des Kadane-Algorithmus:
1. Initialisieren Sie zwei Variablen, max_so_far Und max_ending_here , zum ersten Element des Arrays.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Durchlaufen Sie das Array vom zweiten Element bis zum Ende:
denn ich von 1 bis n-1 mache:
3. Berechnen Sie die maximale Summe, die an der aktuellen Position endet:
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Aktualisieren Sie max_so_far so, dass es das Maximum von max_so_far und max_ending_here ist:
max_so_far = max(max_so_far, max_ending_here)
5. Geben Sie max_so_far als maximale Summe aller Unterarrays im Array zurück.
Die zeitliche Komplexität des Kadane-Algorithmus beträgt O(n), wobei n die Länge des Eingabearrays ist. Dies macht es zu einer sehr effizienten Lösung für das Maximum-Subarray-Problem.
Beispiel:
Sehen wir uns ein Beispiel an, wie Kadanes Algorithmus funktioniert:
Angenommen, wir haben das folgende Array von ganzen Zahlen:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Wir wollen die maximale Subarray-Summe dieses Arrays ermitteln. Wir können Kadanes Algorithmus anwenden, um dieses Problem zu lösen.
Wir beginnen mit der Initialisierung zweier Variablen:
max_so_far = INT_MIN; max_ending_here = 0;
Dann durchlaufen wir das Array, beginnend mit dem zweiten Element:
for i in range(1, len(arr)):
Aktualisieren Sie die aktuelle Summe, indem Sie das aktuelle Element zur vorherigen Summe hinzufügen:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Aktualisieren Sie die bisher gesehene Höchstsumme:
max_so_far = max(max_so_far, max_ending_here)
Bei jeder Iteration aktualisieren wir die aktuelle Summe, indem wir entweder das aktuelle Element zur vorherigen Summe hinzufügen oder ein neues Unterarray am aktuellen Element beginnen. Anschließend aktualisieren wir die bisher gesehene Maximalsumme, indem wir sie mit der aktuellen Summe vergleichen.
Nach dem Durchlaufen des gesamten Arrays ist der Wert von max_so_far die maximale Subarray-Summe des angegebenen Arrays.
Welche Monate sind Q3?
In diesem Beispiel beträgt die maximale Subarray-Summe 6, was dem Subarray [4, -1, 2, 1] entspricht.
Code-Implementierung in Java:
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.print('Enter the size of the array : '); int n=sc.nextInt(); int[] arr=new int[n]; System.out.println('Enter the elements of the array : '); for(int i=0;i<n;i++){ arr[i]="sc.nextInt();" } int max_so_far="Integer.MIN_VALUE,max_ending_here=0;" for(int i="0;i<n;i++)" { max_ending_here+="arr[i];" if(max_so_far<max_ending_here){ if(max_ending_here<0){ max_ending_here="0;" system.out.print('the maximum contiguous sum in the array is : '+max_so_far); < pre> <p> <strong>Output</strong> </p> <pre> Enter the size of the array : 9 Enter the elements of the array : -2 1 -3 4 -1 2 1 -5 4 The Maximum contiguous sum in the array is : 6 </pre> <h3>Code Implementation in C++:</h3> <pre> #include using namespace std; int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(a) / sizeof(a[0]); // Kadane's algorithm int max_so_far = INT_MIN, max_ending_here = 0; for (int i = 0; i <n; i++) { max_ending_here="max_ending_here" + a[i]; if (max_so_far < max_ending_here) max_so_far="max_ending_here;" (max_ending_here 0) } cout << 'maximum contiguous sum in the array is : '<<max_so_far<<endl; return 0; pre> <p> <strong>Output</strong> </p> <pre> Maximum contiguous sum in the array is : 7 </pre> <h2>Advantages and Disadvantages of Kadane's algorithm:</h2> <h3>Advantages of Kadane's Algorithm:</h3> <ul> <tr><td>Efficiency:</td> Kadane's Algorithm has a time complexity of O(n), which makes it very efficient for solving the maximum subarray problem. This makes it a great solution for large datasets. </tr><tr><td>Simplicity:</td> Kadane's Algorithm is relatively easy to understand and implement compared to other algorithms for solving the maximum subarray problem, such as the divide-and-conquer algorithm. </tr><tr><td>Space Complexity:</td> Kadane's Algorithm has a space complexity of O(1), which means it uses a constant amount of memory irrespective of the size of the input array. </tr><tr><td>Dynamic Programming:</td> Kadane's Algorithm is a classic example of dynamic programming, a technique that breaks down a problem into smaller subproblems and stores the solutions to these subproblems to avoid redundant computation. </tr></ul> <h3>Disadvantages of Kadane's Algorithm:</h3> <ul> <tr><td>Only finds sum and not the subarray itself:</td> Kadane's Algorithm only finds the maximum sum of the subarray and not the actual subarray itself. If you need to find the subarray that has the maximum sum, you will need to modify the algorithm accordingly. </tr><tr><td>Does not handle negative numbers well:</td> If an input array has only negative numbers, the algorithm will return the maximum negative number instead of 0. This can be overcome by adding an additional step to the algorithm to check if the array has only negative numbers. </tr><tr><td>Not suitable for non-contiguous subarrays:</td> Kadane's Algorithm is specifically designed for contiguous subarrays and may not be suitable for solving problems that involve non-contiguous subarrays. </tr></ul> <h2>Applications of Kadane's algorithm:</h2> <p>There are some of its applications like the following:</p> <ul> <tr><td>Maximum subarray sum:</td> As we saw in the example above, Kadane's algorithm is used to find the maximum subarray sum of an array of integers. This is a common problem in computer science and has applications in data analysis, financial modeling, and other fields. </tr><tr><td>Stock trading:</td> Kadane's algorithm can be used to find the maximum profit that can be made by buying and selling a stock on a given day. The input to the algorithm is an array of stock prices, and the output is the maximum profit that can be made by buying and selling the stock at different times. </tr><tr><td>Image processing:</td> Kadane's algorithm can be used in image processing applications to find the largest contiguous area of pixels that meet a certain condition, such as having a certain color or brightness. This can be useful for tasks such as object recognition and segmentation. </tr><tr><td>DNA sequencing:</td> Kadane's algorithm can be used in bioinformatics to find the longest subsequence of DNA that meets certain conditions. For example, it can be used to find the longest common subsequence between two DNA sequences or to find the longest subsequence that does not contain certain patterns. </tr><tr><td>Machine learning:</td> Kadane's algorithm can be used in some machine learning applications, such as reinforcement learning and dynamic programming, to find the optimal policy or action sequence that maximizes a reward function. </tr></ul> <p>Therefore, we can say the advantages of Kadane's Algorithm make it a great solution for solving the maximum subarray problem, especially for large datasets. However, its limitations must be considered when using it for specific applications.</p> <hr></n;></pre></n;i++){> Code-Implementierung in C++:
#include using namespace std; int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(a) / sizeof(a[0]); // Kadane's algorithm int max_so_far = INT_MIN, max_ending_here = 0; for (int i = 0; i <n; i++) { max_ending_here="max_ending_here" + a[i]; if (max_so_far < max_ending_here) max_so_far="max_ending_here;" (max_ending_here 0) } cout << \'maximum contiguous sum in the array is : \'<<max_so_far<<endl; return 0; pre> <p> <strong>Output</strong> </p> <pre> Maximum contiguous sum in the array is : 7 </pre> <h2>Advantages and Disadvantages of Kadane's algorithm:</h2> <h3>Advantages of Kadane's Algorithm:</h3> <ul> <tr><td>Efficiency:</td> Kadane's Algorithm has a time complexity of O(n), which makes it very efficient for solving the maximum subarray problem. This makes it a great solution for large datasets. </tr><tr><td>Simplicity:</td> Kadane's Algorithm is relatively easy to understand and implement compared to other algorithms for solving the maximum subarray problem, such as the divide-and-conquer algorithm. </tr><tr><td>Space Complexity:</td> Kadane's Algorithm has a space complexity of O(1), which means it uses a constant amount of memory irrespective of the size of the input array. </tr><tr><td>Dynamic Programming:</td> Kadane's Algorithm is a classic example of dynamic programming, a technique that breaks down a problem into smaller subproblems and stores the solutions to these subproblems to avoid redundant computation. </tr></ul> <h3>Disadvantages of Kadane's Algorithm:</h3> <ul> <tr><td>Only finds sum and not the subarray itself:</td> Kadane's Algorithm only finds the maximum sum of the subarray and not the actual subarray itself. If you need to find the subarray that has the maximum sum, you will need to modify the algorithm accordingly. </tr><tr><td>Does not handle negative numbers well:</td> If an input array has only negative numbers, the algorithm will return the maximum negative number instead of 0. This can be overcome by adding an additional step to the algorithm to check if the array has only negative numbers. </tr><tr><td>Not suitable for non-contiguous subarrays:</td> Kadane's Algorithm is specifically designed for contiguous subarrays and may not be suitable for solving problems that involve non-contiguous subarrays. </tr></ul> <h2>Applications of Kadane's algorithm:</h2> <p>There are some of its applications like the following:</p> <ul> <tr><td>Maximum subarray sum:</td> As we saw in the example above, Kadane's algorithm is used to find the maximum subarray sum of an array of integers. This is a common problem in computer science and has applications in data analysis, financial modeling, and other fields. </tr><tr><td>Stock trading:</td> Kadane's algorithm can be used to find the maximum profit that can be made by buying and selling a stock on a given day. The input to the algorithm is an array of stock prices, and the output is the maximum profit that can be made by buying and selling the stock at different times. </tr><tr><td>Image processing:</td> Kadane's algorithm can be used in image processing applications to find the largest contiguous area of pixels that meet a certain condition, such as having a certain color or brightness. This can be useful for tasks such as object recognition and segmentation. </tr><tr><td>DNA sequencing:</td> Kadane's algorithm can be used in bioinformatics to find the longest subsequence of DNA that meets certain conditions. For example, it can be used to find the longest common subsequence between two DNA sequences or to find the longest subsequence that does not contain certain patterns. </tr><tr><td>Machine learning:</td> Kadane's algorithm can be used in some machine learning applications, such as reinforcement learning and dynamic programming, to find the optimal policy or action sequence that maximizes a reward function. </tr></ul> <p>Therefore, we can say the advantages of Kadane's Algorithm make it a great solution for solving the maximum subarray problem, especially for large datasets. However, its limitations must be considered when using it for specific applications.</p> <hr></n;> Vor- und Nachteile des Kadane-Algorithmus:
Vorteile des Kadane-Algorithmus:
Nachteile des Kadane-Algorithmus:
Anwendungen des Kadane-Algorithmus:
Es gibt einige seiner Anwendungen wie die folgenden:
Daher können wir sagen, dass die Vorteile des Kadane-Algorithmus ihn zu einer großartigen Lösung für die Lösung des Maximum-Subarray-Problems machen, insbesondere für große Datensätze. Bei der Verwendung für bestimmte Anwendungen müssen jedoch seine Einschränkungen berücksichtigt werden.