A Kadane-algoritmus egy dinamikus programozási megközelítés, amelyet a maximális altömb probléma megoldására használnak, amely magában foglalja a maximális összegű összefüggő résztömb megtalálását egy számtömbben. Az algoritmust Jay Kadane javasolta 1984-ben, és időbeli összetettsége O(n).
Kadane algoritmusának története:
A Kadane algoritmusa feltalálójáról, Jay Kadane-ről, a Carnegie Mellon Egyetem számítástechnikai professzoráról kapta a nevét. Az algoritmust először a „Maximum Sum Subarray Problem” című cikkében írta le, amelyet a Journal of the Association for Computing Machinery (ACM) 1984-ben tettek közzé.
A maximális alrendszer megtalálásának problémáját az 1970-es évek óta vizsgálják az informatikusok. Ez egy jól ismert probléma az algoritmustervezés és -elemzés területén, és számos területen alkalmazható, beleértve a jelfeldolgozást, a pénzügyet és a bioinformatikát.
Kadane algoritmusa előtt más algoritmusokat is javasoltak a maximális altömb probléma megoldására, mint például a brute-force megközelítés, amely az összes lehetséges altömböt ellenőrzi, és az oszd meg és uralkodj algoritmus. Ezeknek az algoritmusoknak azonban nagyobb az időbonyolultsága, és kevésbé hatékonyak, mint a Kadane-algoritmus.
Kadane algoritmusát széles körben használják a számítástechnikában, és a dinamikus programozás klasszikus példájává vált. Egyszerűsége, hatékonysága és eleganciája népszerű megoldássá tették a maximális alrendszer problémájára, és értékes eszközzé az algoritmusok tervezésében és elemzésében.
A Kadene-algoritmus működése:
Az algoritmus úgy működik, hogy áthalad a tömbön, és nyomon követi az egyes pozíciókban végződő altömb maximális összegét. Minden i pozícióban két lehetőségünk van: vagy hozzáadjuk az i pozícióban lévő elemet az aktuális maximális altömbhöz, vagy új altömböt indítunk az i pozícióban. E két lehetőség közül a maximum az i pozícióban végződő maximális alsor.
Két változót tartunk fenn, a max_so_far és a max_ending_here, hogy nyomon követhessük az eddig látott maximális összeget, illetve az aktuális pozícióban végződő maximális összeget. Az algoritmus úgy indul, hogy mindkét változót a tömb első elemére állítja. Ezután ismételjük a tömböt a második elemtől a végéig.
Minden i pozícióban frissítjük a max_ending_here értéket úgy, hogy az aktuális elem maximumát vesszük, és az aktuális elemet hozzáadjuk az előző maximum altömbhöz. Ezután frissítjük a max_so_far értéket a max_so_far és a max_ending_here értékre.
Az algoritmus a max_so_far értéket adja vissza, ami a tömb bármely altömbjének maximális összege.
Íme a Kadane-algoritmus lépésről lépésre történő folyamata:
1. Inicializáljon két változót, max_so_far és max_ending_ here , a tömb első eleméhez.
max_so_far = arr[0]
tavaszi felhő
max_ending_here = arr[0]
2. Iteráljon a tömbön a második elemtől a végéig:
i-nél 1-től n-1-ig tegye a következőket:
3. Számítsa ki az aktuális pozícióval végződő maximális összeget:
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Frissítse a max_so_far értéket a max_so_far és a max_ending_here maximális értékre:
max_so_far = max(max_so_far, max_ending_ here)
5. Adja vissza a max_so_far értéket a tömb bármely altömbjének maximális összegeként.
A Kadane-algoritmus időbonyolultsága O(n), ahol n a bemeneti tömb hossza. Ez nagyon hatékony megoldást jelent a maximális alrendszer problémájára.
Példa:
Nézzük meg egy példán, hogyan működik Kadane algoritmusa:
Tegyük fel, hogy a következő egész számok tömbje van:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Meg akarjuk találni ennek a tömbnek a maximális altömb összegét. A probléma megoldására alkalmazhatjuk a Kadane-féle algoritmust.
Kezdjük két változó inicializálásával:
max_so_far = INT_MIN; max_ending_here = 0;
Ezután a második elemtől kezdve iteráljuk a tömböt:
for i in range(1, len(arr)):
Frissítse az aktuális összeget az aktuális elem hozzáadásával az előző összeghez:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Frissítse az eddig látott maximális összeget:
max_so_far = max(max_so_far, max_ending_here)
Minden iterációnál frissítjük az aktuális összeget úgy, hogy hozzáadjuk az aktuális elemet az előző összeghez, vagy új altömböt indítunk az aktuális elemnél. Ezt követően frissítjük az eddig látott maximális összeget, összehasonlítva az aktuális összeggel.
A teljes tömb iterációja után a max_so_far értéke az adott tömb maximális altömb összege lesz.
c karakterláncok tömbje
Ebben a példában a maximális altömb összege 6, ami a [4, -1, 2, 1] altömbnek felel meg.
Kód implementáció Java nyelven:
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++){> Kód implementáció C++ nyelven:
#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;> A Kadane algoritmus előnyei és hátrányai:
A Kadane-algoritmus előnyei:
A Kadane-algoritmus hátrányai:
A Kadane-algoritmus alkalmazásai:
Van néhány alkalmazása, például a következők:
Ezért elmondhatjuk, hogy a Kadane algoritmus előnyei kiváló megoldást jelentenek a maximális alrendszer-probléma megoldására, különösen nagy adathalmazok esetén. A korlátait azonban figyelembe kell venni, amikor speciális alkalmazásokhoz használják.