Kadaneov algoritmus je prístup dynamického programovania používaný na vyriešenie problému maximálneho podpolia, ktorý zahŕňa nájdenie súvislého podpolia s maximálnym súčtom v poli čísel. Algoritmus navrhol Jay Kadane v roku 1984 a má časovú zložitosť O(n).
História Kadaneovho algoritmu:
Algoritmus Kadane je pomenovaný po svojom vynálezcovi Jayovi Kadaneovi, profesorovi počítačovej vedy na Carnegie Mellon University. Algoritmus prvýkrát opísal v článku s názvom „Problém s maximálnym súčtom subarray“ publikovanom v časopise Journal of the Association for Computing Machinery (ACM) v roku 1984.
Problémom nájdenia maximálneho podpolia sa zaoberajú počítačoví vedci od 70. rokov minulého storočia. Je to dobre známy problém v oblasti návrhu a analýzy algoritmov a má uplatnenie v širokej škále oblastí vrátane spracovania signálov, financií a bioinformatiky.
Pred Kadaneovým algoritmom boli navrhnuté iné algoritmy na riešenie problému maximálneho podpolia, ako je prístup hrubej sily, ktorý kontroluje všetky možné podpolia a algoritmus rozdeľuj a panuj. Tieto algoritmy však majú vyššiu časovú zložitosť a sú menej efektívne ako Kadaneov algoritmus.
Kadaneov algoritmus je široko používaný v informatike a stal sa klasickým príkladom dynamického programovania. Jeho jednoduchosť, efektívnosť a elegancia z neho urobili obľúbené riešenie maximálneho problému podpolia a cenný nástroj pri návrhu a analýze algoritmov.
Fungovanie Kadeneovho algoritmu:
Algoritmus funguje tak, že iteruje cez pole a sleduje maximálny súčet čiastkových polí končiacich na každej pozícii. Na každej pozícii i máme dve možnosti: buď pridať prvok na pozícii i do aktuálneho maximálneho podpola alebo začať nové podpole na pozícii i. Maximum z týchto dvoch možností je maximálne podpole končiace na pozícii i.
Udržujeme dve premenné, max_so_far a max_ending_here, aby sme sledovali maximálny súčet, ktorý sme doteraz videli, a maximálny súčet končiaci na aktuálnej pozícii. Algoritmus začína nastavením oboch premenných na prvý prvok poľa. Potom iterujeme cez pole od druhého prvku až po koniec.
Na každej pozícii i aktualizujeme max_ending_here tak, že zoberieme maximum aktuálneho prvku a aktuálny prvok pridaný do predchádzajúceho maximálneho podpola. Potom aktualizujeme max_so_far na maximum z max_so_far a max_ending_here.
Algoritmus vráti max_so_far, čo je maximálny súčet akéhokoľvek podpola v poli.
Tu je krok za krokom proces Kadaneovho algoritmu:
1. Inicializujte dve premenné, max_so_far a max_ending_tu , na prvý prvok poľa.
max_so_far = arr[0]
protokoly vrstvy dátového spojenia
max_ending_here = arr[0]
2. Iterujte pole od druhého prvku až po koniec:
pre ja od 1 do n-1 urob:
3. Vypočítajte maximálny súčet končiaci na aktuálnej pozícii:
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Aktualizujte max_so_far na maximum z max_so_far a max_ending_here:
max_so_far = max(max_so_far, max_ending_here)
5. Vráťte max_so_far ako maximálny súčet akéhokoľvek podpola v poli.
Časová zložitosť Kadaneovho algoritmu je O(n), kde n je dĺžka vstupného poľa. To z neho robí veľmi efektívne riešenie maximálneho problému podpolia.
Príklad:
Pozrime sa na príklade, ako funguje Kadaneov algoritmus:
Predpokladajme, že máme nasledujúce pole celých čísel:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Chceme nájsť maximálny súčet čiastkových polí tohto poľa. Na vyriešenie tohto problému môžeme použiť Kadaneov algoritmus.
Začneme inicializáciou dvoch premenných:
max_so_far = INT_MIN; max_ending_here = 0;
Potom iterujeme cez pole, počnúc druhým prvkom:
for i in range(1, len(arr)):
Aktualizujte aktuálny súčet pridaním aktuálneho prvku k predchádzajúcemu súčtu:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Aktualizujte doteraz zobrazenú maximálnu sumu:
max_so_far = max(max_so_far, max_ending_here)
Pri každej iterácii aktualizujeme aktuálny súčet buď pridaním aktuálneho prvku k predchádzajúcemu súčtu alebo spustením nového podpola v aktuálnom prvku. Potom aktualizujeme maximálnu sumu, ktorú sme doteraz videli, porovnaním s aktuálnou sumou.
Po iterácii cez celé pole bude hodnota max_so_far maximálnym súčtom podpola daného poľa.
V tomto príklade je maximálny súčet podpola 6, čo zodpovedá podpole [4, -1, 2, 1].
Implementácia kódu v jazyku 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++){> Implementácia kódu v 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;> Výhody a nevýhody Kadaneovho algoritmu:
Výhody Kadaneovho algoritmu:
Nevýhody Kadaneovho algoritmu:
Aplikácie Kadaneovho algoritmu:
Existujú niektoré z jeho aplikácií, ako napríklad:
Preto môžeme povedať, že výhody Kadaneovho algoritmu z neho robia skvelé riešenie na riešenie maximálneho problému podpolia, najmä pre veľké súbory údajov. Pri použití na špecifické aplikácie je však potrebné zvážiť jeho obmedzenia.