Kadane'o algoritmas yra dinaminis programavimo metodas, naudojamas didžiausios pogrupio problemos sprendimui, kuris apima gretimo pogrupio su didžiausia skaičių masyve radimą. Algoritmą pasiūlė Jay Kadane 1984 m., jo sudėtingumas yra O (n).
Kadane algoritmo istorija:
Kadane'o algoritmas pavadintas jo išradėjo Jay Kadane, Carnegie Mellon universiteto kompiuterių mokslų profesoriaus, vardu. Jis pirmą kartą aprašė algoritmą darbe, pavadintame „Maksimalios sumos subarray problema“, paskelbtame Kompiuterinių mašinų asociacijos žurnale (ACM) 1984 m.
Didžiausio pogrupio radimo problemą kompiuterių mokslininkai tyrinėjo nuo 1970 m. Tai gerai žinoma problema algoritmų projektavimo ir analizės srityje ir taikoma įvairiose srityse, įskaitant signalų apdorojimą, finansus ir bioinformatiką.
latekso šriftas
Iki Kadane'o algoritmo buvo pasiūlyti ir kiti algoritmai, skirti maksimaliai subarstyto problemai išspręsti, pavyzdžiui, brute-force metodas, kuris patikrina visas įmanomas pogrupes ir dalyk ir užkariauk algoritmas. Tačiau šie algoritmai turi didesnį laiko sudėtingumą ir yra mažiau veiksmingi nei Kadane algoritmas.
Kadane'o algoritmas plačiai naudojamas informatikos moksle ir tapo klasikiniu dinaminio programavimo pavyzdžiu. Dėl savo paprastumo, efektyvumo ir elegancijos jis tapo populiariu didžiausios pogrupio problemos sprendimu ir vertingu įrankiu kuriant ir analizuojant algoritmus.
Kadene algoritmo veikimas:
Algoritmas veikia kartodamas masyvą ir sekdamas maksimalią pogrupio, kuris baigiasi kiekvienoje padėtyje, sumą. Kiekvienoje i padėtyje turime dvi parinktis: arba pridėti elementą, esantį i padėtyje, prie dabartinės didžiausios pogrupio arba pradėti naują pogrupį i padėtyje. Didžiausias iš šių dviejų variantų yra didžiausias pogrupis, kuris baigiasi i padėtyje.
Mes palaikome du kintamuosius max_so_far ir max_ending_here, kad galėtume sekti atitinkamai didžiausią iki šiol matytą sumą ir maksimalią sumą, kurios pabaiga yra dabartinė padėtis. Algoritmas pradedamas nustatant abu kintamuosius pirmajam masyvo elementui. Tada kartojame masyvą nuo antrojo elemento iki pabaigos.
css sąrašus
Kiekvienoje padėtyje i mes atnaujiname max_ending_here, paimdami maksimalų dabartinį elementą ir dabartinį elementą, pridėtą prie ankstesnio didžiausio pogrupio. Tada atnaujiname max_so_far į maksimalų skaičių max_so_far ir max_ending_here.
Algoritmas grąžina max_so_far, kuri yra didžiausia bet kurio masyvo pogrupio suma.
Štai žingsnis po žingsnio Kadane'o algoritmo procesas:
1. Inicijuoti du kintamuosius, max_iki šiol ir max_ending_čia , į pirmąjį masyvo elementą.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Pakartokite masyvą nuo antrojo elemento iki pabaigos:
i nuo 1 iki n-1 darykite:
abstrakčioje klasėje gali būti konstruktorius
3. Apskaičiuokite didžiausią sumą, kuri baigiasi dabartine padėtimi:
max_ending_here = max (arr[i], max_ending_here + arr[i])
4. Atnaujinkite max_so_far, kad būtų maksimalus max_so_far ir max_ending_here:
max_so_far = max (maks._iki_toli, maks._pabaiga_čia)
5. Grąžinkite max_so_far maksimalią bet kurio masyvo pogrupio sumą.
Kadane'o algoritmo laiko sudėtingumas yra O(n), kur n yra įvesties masyvo ilgis. Dėl to jis yra labai efektyvus didžiausios pogrupio problemos sprendimas.
abstrakcija java
Pavyzdys:
Pažiūrėkime, kaip veikia Kadane algoritmas:
Tarkime, kad turime tokį sveikųjų skaičių masyvą:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Norime rasti didžiausią šio masyvo pogrupio sumą. Šiai problemai išspręsti galime pritaikyti Kadane algoritmą.
Pradedame inicijuodami du kintamuosius:
max_so_far = INT_MIN; max_ending_here = 0;
Tada kartojame masyvą, pradedant nuo antrojo elemento:
for i in range(1, len(arr)):
Atnaujinkite dabartinę sumą pridėdami dabartinį elementą prie ankstesnės sumos:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Atnaujinti maksimalią iki šiol matytą sumą:
dar java
max_so_far = max(max_so_far, max_ending_here)
Kiekvienos iteracijos metu esamą sumą atnaujiname pridėdami dabartinį elementą prie ankstesnės sumos arba pradėdami naują pogrupį nuo dabartinio elemento. Tada atnaujiname maksimalią iki šiol matytą sumą, lygindami ją su dabartine suma.
Pakartojus visą masyvą, max_so_far reikšmė bus didžiausia nurodyto masyvo pogrupio suma.
Šiame pavyzdyje didžiausia pogrupio suma yra 6, o tai atitinka pogrupį [4, -1, 2, 1].
Kodo diegimas 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++){> Kodo įgyvendinimas 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;> Kadane algoritmo privalumai ir trūkumai:
Kadane algoritmo pranašumai:
Kadane algoritmo trūkumai:
Kadane algoritmo taikymas:
Yra keletas jo programų, pavyzdžiui, šios:
Todėl galime teigti, kad Kadane's Algorithm pranašumai daro jį puikiu sprendimu sprendžiant maksimalios pogrupio problemą, ypač esant dideliems duomenų rinkiniams. Tačiau naudojant jį konkrečioms reikmėms, reikia atsižvelgti į jo apribojimus.