Kadanejev algoritem je pristop dinamičnega programiranja, ki se uporablja za reševanje problema maksimalne podmatrike, ki vključuje iskanje sosednje podmatrike z največjo vsoto v nizu števil. Algoritem je predlagal Jay Kadane leta 1984 in ima časovno kompleksnost O(n).
Zgodovina Kadanejevega algoritma:
Kadanov algoritem je dobil ime po svojem izumitelju Jayu Kadanu, profesorju računalništva na univerzi Carnegie Mellon. Algoritem je prvič opisal v članku z naslovom 'Maximum Sum Subarray Problem', objavljenem v Journal of Association for Computing Machinery (ACM) leta 1984.
Problem iskanja največjega podniza so računalniški znanstveniki preučevali že od sedemdesetih let prejšnjega stoletja. To je dobro znan problem na področju oblikovanja in analize algoritmov in ima aplikacije na številnih področjih, vključno z obdelavo signalov, financami in bioinformatiko.
t ff
Pred Kadanejevim algoritmom so bili predlagani drugi algoritmi za reševanje problema maksimalne podmatriže, kot je pristop s surovo silo, ki preverja vse možne podmatriže, in algoritem deli in vladaj. Vendar imajo ti algoritmi večjo časovno kompleksnost in so manj učinkoviti od Kadanejevega algoritma.
Kadanejev algoritem se pogosto uporablja v računalništvu in je postal klasičen primer dinamičnega programiranja. Zaradi svoje preprostosti, učinkovitosti in elegance je postala priljubljena rešitev problema maksimalne podmatrike in dragoceno orodje pri načrtovanju in analizi algoritmov.
Delovanje Kadenovega algoritma:
Algoritem deluje tako, da ponavlja matriko in spremlja največjo vsoto podmatrike, ki se konča na vsakem položaju. Na vsaki poziciji i imamo dve možnosti: bodisi dodati element na poziciji i v trenutno največjo podmatriko ali začeti novo podmatrico na poziciji i. Največja od teh dveh možnosti je največja podmatrika, ki se konča na položaju i.
Vzdržujemo dve spremenljivki, max_so_far in max_ending_here, da spremljamo največjo vsoto, ki smo jo videli do zdaj, oziroma največjo vsoto, ki se konča na trenutnem položaju. Algoritem se začne z nastavitvijo obeh spremenljivk na prvi element matrike. Nato ponovimo matriko od drugega elementa do konca.
Na vsakem položaju i posodobimo max_ending_here tako, da vzamemo maksimum trenutnega elementa in trenutni element, dodan prejšnjemu maksimalnemu podnizu. Nato posodobimo max_so_far, da je največja vrednost max_so_far in max_ending_here.
Algoritem vrne max_so_far, kar je največja vsota katere koli podmatrike v matriki.
Tukaj je korak za korakom postopek Kadanejevega algoritma:
1. Inicializirajte dve spremenljivki, max_so_far in max_ending_here , na prvi element matrike.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Ponovite matriko od drugega elementa do konca:
za i od 1 do n-1 naredite:
3. Izračunajte največjo vsoto, ki se konča na trenutnem položaju:
drevesni zemljevid
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Posodobite max_so_far tako, da bo največja vrednost max_so_far in max_ending_here:
max_tako_daleč = max(max_so_daleč, max_ending_here)
5. Vrne max_so_far kot največjo vsoto katere koli podmatrike v matriki.
Časovna kompleksnost Kadanovega algoritma je O(n), kjer je n dolžina vhodnega niza. Zaradi tega je zelo učinkovita rešitev problema maksimalne podmatrike.
primer:
Poglejmo na primeru, kako deluje Kadaneov algoritem:
Recimo, da imamo naslednjo matriko celih števil:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Najti želimo največjo vsoto podmatrice te matrike. Za rešitev tega problema lahko uporabimo Kadaneov algoritem.
Začnemo z inicializacijo dveh spremenljivk:
max_so_far = INT_MIN; max_ending_here = 0;
Nato ponovimo matriko, začenši z drugim elementom:
for i in range(1, len(arr)):
Posodobite trenutno vsoto tako, da dodate trenutni element prejšnji vsoti:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Posodobite najvišjo do zdaj videno vsoto:
max_so_far = max(max_so_far, max_ending_here)
Pri vsaki ponovitvi posodobimo trenutno vsoto tako, da trenutni element dodamo prejšnji vsoti ali začnemo novo podmatriko pri trenutnem elementu. Nato posodobimo najvišjo do sedaj videno vsoto tako, da jo primerjamo s trenutno vsoto.
Po ponovitvi skozi celotno matriko bo vrednost max_so_far največja vsota podmatrike dane matrike.
V tem primeru je največja vsota podniza 6, kar ustreza podmatriži [4, -1, 2, 1].
niz nizov
Implementacija kode v Javi:
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++){> Implementacija kode 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;> Prednosti in slabosti Kadanovega algoritma:
Prednosti Kadanovega algoritma:
Slabosti Kadanovega algoritma:
Uporaba Kadanovega algoritma:
Obstaja nekaj njegovih aplikacij, kot so:
Zato lahko rečemo, da je zaradi prednosti Kadanovega algoritma odlična rešitev za reševanje problema maksimalne podmatrike, zlasti za velike nabore podatkov. Vendar je treba upoštevati njegove omejitve, ko ga uporabljate za posebne aplikacije.