Kadane algoritms ir dinamiska programmēšanas pieeja, ko izmanto, lai atrisinātu maksimālo apakšmasu problēmu, kas ietver blakus esošā apakšmasīva atrašanu ar maksimālo summu skaitļu masīvā. Algoritmu ierosināja Džejs Kadens 1984. gadā, un tā laika sarežģītība ir O(n).
Kadanes algoritma vēsture:
Kadanes algoritms ir nosaukts tā izgudrotāja Džeja Kadana, Kārnegija Melona universitātes datorzinātņu profesora, vārdā. Viņš pirmo reizi aprakstīja algoritmu rakstā ar nosaukumu “Maksimālās summas apakšreižu problēma”, kas publicēts skaitļošanas tehnikas asociācijas (ACM) žurnālā 1984. gadā.
Maksimālā apakšgrupas atrašanas problēmu datorzinātnieki ir pētījuši kopš pagājušā gadsimta 70. gadiem. Tā ir labi zināma problēma algoritmu izstrādes un analīzes jomā, un tai ir pielietojums daudzās jomās, tostarp signālu apstrādē, finansēs un bioinformātikā.
Pirms Kadanes algoritma maksimālās apakšgrupas problēmas risināšanai tika piedāvāti citi algoritmi, piemēram, brutālā spēka pieeja, kas pārbauda visus iespējamos apakšgrupas, un dalīšanas un iekarošanas algoritms. Tomēr šiem algoritmiem ir lielāka laika sarežģītība un tie ir mazāk efektīvi nekā Kadane algoritms.
Kadanes algoritms tiek plaši izmantots datorzinātnēs un ir kļuvis par klasisku dinamiskās programmēšanas piemēru. Tā vienkāršība, efektivitāte un elegance ir padarījusi to par populāru risinājumu maksimālās apakšgrupas problēmai un vērtīgu rīku algoritmu izstrādē un analīzē.
Kadenes algoritma darbība:
Algoritms darbojas, atkārtojot masīvu un sekojot līdzi apakšmasīva maksimālajai summai, kas beidzas katrā pozīcijā. Katrā pozīcijā i mums ir divas iespējas: vai nu pievienot elementu pozīcijā i pašreizējam maksimālajam apakšgrupam vai sākt jaunu apakšgrupu pozīcijā i. Maksimālais no šiem diviem variantiem ir maksimālais apakšgrupas, kas beidzas pozīcijā i.
Mēs uzturam divus mainīgos, max_so_far un max_ending_here, lai izsekotu attiecīgi līdz šim redzētajai maksimālajai summai un maksimālajai summai, kas beidzas pašreizējā pozīcijā. Algoritms sākas ar abu mainīgo iestatīšanu pirmajam masīva elementam. Pēc tam mēs atkārtojam masīvu no otrā elementa līdz beigām.
Katrā pozīcijā i mēs atjauninām max_ending_here, ņemot pašreizējā elementa maksimumu un pašreizējo elementu, kas pievienots iepriekšējam maksimālajam apakšgrupam. Pēc tam mēs atjauninām max_so_far, lai tas būtu maksimālais no max_so_far un max_ending_here.
Linux mainīt direktorija nosaukumu
Algoritms atgriež max_so_far, kas ir jebkura masīva apakšmasīva maksimālā summa.
Lūk, soli pa solim Kadanes algoritma process:
1. Inicializējiet divus mainīgos, max_so_far un max_beigas_šeit , uz pirmo masīva elementu.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Atkārtojiet masīvu no otrā elementa līdz beigām:
i no 1 līdz n-1 rīkojieties šādi:
3. Aprēķiniet maksimālo summu, kas beidzas pašreizējā pozīcijā:
tkinter poga
max_beigas_šeit = max(arr[i], max_beigas_šeit + arr[i])
4. Atjauniniet parametrus max_so_far, lai tas būtu maksimālais no max_so_far un max_ending_here:
max_so_far = max(max_so_far, max_beigas_šeit)
5. Atgriež max_so_far kā jebkura masīva apakšmasīva maksimālo summu.
Kadane algoritma laika sarežģītība ir O(n), kur n ir ievades masīva garums. Tas padara to par ļoti efektīvu risinājumu maksimālās apakšgrupas problēmai.
Piemērs:
Apskatīsim piemēru, kā darbojas Kadanes algoritms:
Pieņemsim, ka mums ir šāds veselu skaitļu masīvs:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Mēs vēlamies atrast šī masīva maksimālo apakšmasīva summu. Lai atrisinātu šo problēmu, mēs varam izmantot Kadanes algoritmu.
Mēs sākam, inicializējot divus mainīgos:
max_so_far = INT_MIN; max_ending_here = 0;
Pēc tam mēs atkārtojam masīvu, sākot no otrā elementa:
java listbox
for i in range(1, len(arr)):
Atjauniniet pašreizējo summu, pievienojot pašreizējo elementu iepriekšējai summai:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Atjauniniet līdz šim redzēto maksimālo summu:
max_so_far = max(max_so_far, max_ending_here)
Katrā iterācijā mēs atjauninām pašreizējo summu, pievienojot pašreizējo elementu iepriekšējai summai vai sākot jaunu apakšgrupu pie pašreizējā elementa. Pēc tam mēs atjauninām līdz šim redzēto maksimālo summu, salīdzinot to ar pašreizējo summu.
Pēc atkārtošanas visā masīvā max_so_far vērtība būs dotā masīva maksimālā apakšmasīva summa.
Šajā piemērā maksimālā apakšmasīva summa ir 6, kas atbilst apakšmasīvam [4, -1, 2, 1].
Koda ieviešana 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++){> Koda ieviešana C++ valodā:
#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;> Kadanes algoritma priekšrocības un trūkumi:
Kadanes algoritma priekšrocības:
Kadanes algoritma trūkumi:
Kadanes algoritma pielietojumi:
Ir dažas tās lietojumprogrammas, piemēram:
Tāpēc mēs varam teikt, ka Kadane algoritma priekšrocības padara to par lielisku risinājumu maksimālās apakšgrupas problēmas risināšanai, īpaši lielām datu kopām. Tomēr, lietojot to īpašiem lietojumiem, jāņem vērā tā ierobežojumi.