Kadanen algoritmi on dynaaminen ohjelmointitapa, jota käytetään ratkaisemaan suurimman alitaulukon ongelma, joka sisältää vierekkäisen alitaulukon, jonka suurin summa on lukujen joukosta. Algoritmia ehdotti Jay Kadane vuonna 1984, ja sen aikamonimutkaisuus on O(n).
Kadanen algoritmin historia:
Kadanen algoritmi on nimetty sen keksijän, Carnegie Mellonin yliopiston tietojenkäsittelytieteen professorin Jay Kadanen mukaan. Hän kuvaili algoritmia ensimmäisen kerran artikkelissa 'Maximum Sum Subarray Problem', joka julkaistiin Journal of the Association for Computing Machinery (ACM) -lehdessä vuonna 1984.
Tietojenkäsittelytieteilijät ovat tutkineet suurimman aliryhmän löytämisen ongelmaa 1970-luvulta lähtien. Se on hyvin tunnettu ongelma algoritmien suunnittelun ja analyysin alalla, ja sillä on sovelluksia monilla aloilla, mukaan lukien signaalinkäsittely, rahoitus ja bioinformatiikka.
java-koodiesimerkkejä
Ennen Kadanen algoritmia oli ehdotettu muita algoritmeja maksimialiryhmien ongelman ratkaisemiseksi, kuten raakavoima-lähestymistapa, joka tarkistaa kaikki mahdolliset aliryhmät ja jaa ja hallitse -algoritmi. Näillä algoritmeilla on kuitenkin korkeampi aikamonimutkaisuus ja ne ovat vähemmän tehokkaita kuin Kadanen algoritmi.
Kadanen algoritmia käytetään laajalti tietojenkäsittelytieteessä ja siitä on tullut klassinen esimerkki dynaamisesta ohjelmoinnista. Sen yksinkertaisuus, tehokkuus ja tyylikkyys ovat tehneet siitä suositun ratkaisun suurimman osajärjestelmän ongelmaan ja arvokkaan työkalun algoritmien suunnittelussa ja analysoinnissa.
Kadenen algoritmin toiminta:
Algoritmi toimii iteroimalla taulukon yli ja pitämällä kirjaa kuhunkin kohtaan päättyvän alitaulukon maksimisummasta. Jokaisessa kohdassa i meillä on kaksi vaihtoehtoa: joko lisätä asemassa i oleva elementti nykyiseen maksimialitaulukkoon tai aloittaa uusi aliryhmä paikasta i. Näistä kahdesta vaihtoehdosta suurin on suurin aliryhmä, joka päättyy kohtaan i.
Ylläpidämme kahta muuttujaa, max_so_far ja max_ending_here, seurataksemme tähän mennessä nähtyä maksimisummaa ja vastaavasti nykyiseen sijaintiin päättyvää enimmäissummaa. Algoritmi alkaa asettamalla molemmat muuttujat taulukon ensimmäiselle elementille. Sitten iteroimme taulukon yli toisesta elementistä loppuun.
Päivitämme kussakin kohdassa i max_ending_here ottamalla nykyisen elementin maksimin ja nykyisen elementin lisättynä edelliseen maksimialitaulukkoon. Päivitämme sitten max_so_far maksimiarvoksi max_so_far ja max_ending_here.
Algoritmi palauttaa max_so_far, joka on taulukon minkä tahansa alitaulukon enimmäissumma.
Tässä on Kadanen algoritmin vaiheittainen prosessi:
1. Alusta kaksi muuttujaa, max_tofar_far ja max_ending_ here , taulukon ensimmäiseen elementtiin.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Toista taulukkoa toisesta elementistä loppuun:
i 1:stä n-1:een tee:
3. Laske maksimisumma, joka päättyy nykyiseen sijaintiin:
pöydät lateksia
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Päivitä max_so_far maksimiarvoksi max_so_far ja max_ending_here:
max_so_far = max(max_so_far, max_ending_ here)
5. Palauta max_so_far minkä tahansa taulukon alitaulukon maksimisumma.
Kadanen algoritmin aikamonimutkaisuus on O(n), missä n on syötetaulukon pituus. Tämä tekee siitä erittäin tehokkaan ratkaisun suurimman alijärjestelmän ongelmaan.
Esimerkki:
Katsotaanpa esimerkissä, kuinka Kadanen algoritmi toimii:
Oletetaan, että meillä on seuraava kokonaislukutaulukko:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Haluamme löytää tämän taulukon suurimman alitaulukon summan. Voimme soveltaa Kadanen algoritmia tämän ongelman ratkaisemiseen.
Aloitamme alustamalla kaksi muuttujaa:
max_so_far = INT_MIN; max_ending_here = 0;
Sitten iteroidaan taulukkoa alkaen toisesta elementistä:
for i in range(1, len(arr)):
Päivitä nykyinen summa lisäämällä nykyinen elementti edelliseen summaan:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Päivitä tähän mennessä nähty enimmäissumma:
max_so_far = max(max_so_far, max_ending_here)
Jokaisessa iteraatiossa päivitämme nykyisen summan joko lisäämällä nykyisen elementin edelliseen summaan tai aloittamalla uuden alitaulukon nykyisestä elementistä. Päivitämme sitten tähän mennessä nähdyn maksimisumman vertaamalla sitä nykyiseen summaan.
Koko taulukon iteroinnin jälkeen arvo max_so_far on annetun taulukon suurin alitaulukkosumma.
Tässä esimerkissä alitaulukon maksimisumma on 6, mikä vastaa alitaulukkoa [4, -1, 2, 1].
bash-kielen pituus
Koodin toteutus Javassa:
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++){> Koodin toteutus C++:ssa:
#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;> Kadanen algoritmin edut ja haitat:
Kadanen algoritmin edut:
Kadanen algoritmin haitat:
Kadanen algoritmin sovellukset:
Siellä on joitain sen sovelluksia, kuten seuraavat:
Siksi voimme sanoa, että Kadanen algoritmin edut tekevät siitä erinomaisen ratkaisun suurimman aliryhmän ongelman ratkaisemiseen, erityisesti suurille tietojoukoille. Sen rajoitukset on kuitenkin otettava huomioon, kun sitä käytetään tiettyihin sovelluksiin.