Algoritmul lui Kadane este o abordare de programare dinamică utilizată pentru a rezolva problema maximă subbary, care implică găsirea subbaryului contiguu cu suma maximă într-o matrice de numere. Algoritmul a fost propus de Jay Kadane în 1984 și are o complexitate în timp de O(n).
Istoria algoritmului lui Kadane:
Algoritmul lui Kadane poartă numele inventatorului său, Jay Kadane, profesor de informatică la Universitatea Carnegie Mellon. El a descris pentru prima dată algoritmul într-o lucrare intitulată „Problema sumei maxime” publicată în Journal of the Association for Computing Machinery (ACM) în 1984.
Problema găsirii subbarajului maxim a fost studiată de informaticieni încă din anii 1970. Este o problemă binecunoscută în domeniul proiectării și analizei algoritmilor și are aplicații într-o gamă largă de domenii, inclusiv procesarea semnalului, finanțe și bioinformatică.
Înainte de algoritmul lui Kadane, au fost propuși și alți algoritmi pentru rezolvarea problemei maxime subbary, cum ar fi abordarea brute-force care verifică toate subbary-urile posibile și algoritmul divide-and-cuquer. Cu toate acestea, acești algoritmi au complexități de timp mai mari și sunt mai puțin eficienți decât algoritmul lui Kadane.
Algoritmul lui Kadane este utilizat pe scară largă în informatică și a devenit un exemplu clasic de programare dinamică. Simplitatea, eficiența și eleganța sa au făcut din acesta o soluție populară la problema maximă sub-bary și un instrument valoros în proiectarea și analiza algoritmilor.
Funcționarea algoritmului lui Kadene:
Algoritmul funcționează prin iterarea matricei și ținând evidența sumei maxime a subbarajului care se termină la fiecare poziție. La fiecare poziție i, avem două opțiuni: fie adăugați elementul din poziția i la sub-taxa maximă curentă, fie porniți o nouă sub-tază la poziția i. Maximul dintre aceste două opțiuni este subbarra maximă care se termină la poziția i.
Menținem două variabile, max_so_far și max_ending_here, pentru a ține evidența sumei maxime văzute până acum și respectiv a sumei maxime care se termină la poziția curentă. Algoritmul începe prin setarea ambelor variabile la primul element al matricei. Apoi, iterăm peste matrice de la al doilea element până la sfârșit.
La fiecare poziție i, actualizăm max_ending_here luând maximul elementului curent și elementul curent adăugat la subbarajul maxim anterior. Apoi actualizăm max_so_far pentru a fi maximul de max_so_far și max_ending_here.
Algoritmul returnează max_so_far, care este suma maximă a oricărui subbary din matrice.
Iată procesul pas cu pas al algoritmului lui Kadane:
1. Inițializați două variabile, max_pâna_fara și max_se termina aici , la primul element al matricei.
max_to_far = arr[0]
max_ending_here = arr[0]
2. Iterați peste matrice de la al doilea element până la sfârșit:
pentru i de la 1 la n-1 fac:
3. Calculați suma maximă care se termină la poziția curentă:
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Actualizați max_so_far pentru a fi maximul de max_so_far și max_ending_here:
max_to_far = max(max_to_far, max_ending_here)
5. Întoarce max_to_far ca suma maximă a oricărui subbary din matrice.
Complexitatea temporală a algoritmului lui Kadane este O(n), unde n este lungimea matricei de intrare. Acest lucru îl face o soluție foarte eficientă la problema maximă subbarray.
Exemplu:
Să vedem un exemplu despre cum funcționează algoritmul lui Kadane:
Să presupunem că avem următoarea matrice de numere întregi:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Vrem să găsim suma maximă sub-tabelă a acestui tablou. Putem aplica algoritmul lui Kadane pentru a rezolva această problemă.
Începem prin a inițializa două variabile:
max_so_far = INT_MIN; max_ending_here = 0;
Apoi, iterăm prin matrice, pornind de la al doilea element:
for i in range(1, len(arr)):
Actualizați suma curentă adăugând elementul curent la suma anterioară:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Actualizați suma maximă văzută până acum:
max_so_far = max(max_so_far, max_ending_here)
La fiecare iterație, actualizăm suma curentă fie adăugând elementul curent la suma anterioară, fie pornind un nou subbary la elementul curent. Apoi actualizăm suma maximă văzută până acum comparând-o cu suma actuală.
După iterarea întregii matrice, valoarea lui max_so_far va fi suma maximă a matricei date.
În acest exemplu, suma maximă a subgrupului este 6, ceea ce corespunde subgrupului [4, -1, 2, 1].
șir în char java
Implementarea codului în 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++){> Implementarea codului în 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;> Avantajele și dezavantajele algoritmului lui Kadane:
Avantajele algoritmului lui Kadane:
Dezavantajele algoritmului lui Kadane:
Aplicații ale algoritmului lui Kadane:
Există câteva dintre aplicațiile sale, cum ar fi următoarele:
Prin urmare, putem spune că avantajele algoritmului lui Kadane îl fac o soluție excelentă pentru rezolvarea problemei maxime subbary, în special pentru seturile de date mari. Cu toate acestea, limitările sale trebuie luate în considerare atunci când îl utilizați pentru aplicații specifice.