L'algorisme de Kadane és un enfocament de programació dinàmica que s'utilitza per resoldre el problema de la subarray màxima, que consisteix a trobar la subarray contigu amb la suma màxima en una matriu de nombres. L'algorisme va ser proposat per Jay Kadane el 1984 i té una complexitat temporal de O(n).
Història de l'algorisme de Kadane:
L'algoritme de Kadane rep el nom del seu inventor, Jay Kadane, professor d'informàtica a la Universitat Carnegie Mellon. Va descriure per primera vegada l'algoritme en un article titulat 'Maximum Sum Subarray Problem' publicat al Journal of the Association for Computing Machinery (ACM) el 1984.
El problema de trobar el màxim subarray ha estat estudiat pels informàtics des de la dècada de 1970. És un problema conegut en el camp del disseny i anàlisi d'algoritmes i té aplicacions en una àmplia gamma d'àrees, com ara el processament de senyals, les finances i la bioinformàtica.
anotacions a Spring Boot
Abans de l'algoritme de Kadane, s'havien proposat altres algorismes per resoldre el problema del màxim subbarray, com l'enfocament de força bruta que verifica tots els subbarrays possibles i l'algoritme de dividir i conquerir. Tanmateix, aquests algorismes tenen més complexitat de temps i són menys eficients que l'algoritme de Kadane.
L'algoritme de Kadane s'utilitza àmpliament en informàtica i s'ha convertit en un exemple clàssic de programació dinàmica. La seva senzillesa, eficiència i elegància l'han convertit en una solució popular per al problema màxim de subarray i en una valuosa eina en el disseny i l'anàlisi d'algorismes.
Funcionament de l'algoritme de Kadene:
L'algorisme funciona iterant sobre la matriu i fent un seguiment de la suma màxima de la subbarra que acaba a cada posició. A cada posició i, tenim dues opcions: o bé afegir l'element a la posició i al subbarrat màxim actual o iniciar un nou subbarrat a la posició i. El màxim d'aquestes dues opcions és el subbarrat màxim que acaba a la posició i.
Mantenim dues variables, max_so_far i max_ending_here, per fer un seguiment de la suma màxima vista fins ara i la suma màxima que acaba a la posició actual, respectivament. L'algorisme comença establint ambdues variables al primer element de la matriu. A continuació, iterem sobre la matriu des del segon element fins al final.
A cada posició i, actualitzem max_ending_here agafant el màxim de l'element actual i l'element actual afegit al subbarray màxim anterior. A continuació, actualitzem max_so_far perquè sigui el màxim de max_so_far i max_ending_here.
L'algorisme retorna max_so_far, que és la suma màxima de qualsevol subarray de la matriu.
Aquí teniu el procés pas a pas de l'algoritme de Kadane:
1. Inicialitzar dues variables, max_fins_aquí i max_ending_aquí , al primer element de la matriu.
max_fins_alors = arr[0]
max_ending_here = arr[0]
2. Recorre la matriu des del segon element fins al final:
per i de 1 a n-1 fer:
3. Calcula la suma màxima que acaba a la posició actual:
vaja en java
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Actualitzeu max_so_far perquè sigui el màxim de max_so_far i max_ending_here:
max_fins_all = màx (max_fins, max_ending_aquí)
5. Retorna max_fins_que la suma màxima de qualsevol subarray de la matriu.
La complexitat temporal de l'algoritme de Kadane és O(n), on n és la longitud de la matriu d'entrada. Això fa que sigui una solució molt eficient per al problema màxim de subarray.
Exemple:
Vegem un exemple de com funciona l'algoritme de Kadane:
Suposem que tenim la següent matriu d'enters:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Volem trobar la suma màxima de subarray d'aquesta matriu. Podem aplicar l'algorisme de Kadane per resoldre aquest problema.
Comencem inicialitzant dues variables:
max_so_far = INT_MIN; max_ending_here = 0;
A continuació, iterem per la matriu, començant pel segon element:
for i in range(1, len(arr)):
Actualitzeu la suma actual afegint l'element actual a la suma anterior:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Actualitzeu la suma màxima vista fins ara:
max_so_far = max(max_so_far, max_ending_here)
A cada iteració, actualitzem la suma actual afegint l'element actual a la suma anterior o iniciant una nova subbarra a l'element actual. A continuació, actualitzem la suma màxima vista fins ara comparant-la amb la suma actual.
Després d'iterar per tota la matriu, el valor de max_so_far serà la suma màxima de subarray de la matriu donada.
En aquest exemple, la suma màxima del subbarrat és 6, que correspon al subbarray [4, -1, 2, 1].
java for bucle
Implementació de codi en 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++){> Implementació de codi en 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;> Avantatges i desavantatges de l'algoritme de Kadane:
Avantatges de l'algoritme de Kadane:
Desavantatges de l'algoritme de Kadane:
Aplicacions de l'algorisme de Kadane:
Hi ha algunes de les seves aplicacions com les següents:
Per tant, podem dir que els avantatges de l'algoritme de Kadane el converteixen en una gran solució per resoldre el problema màxim de subarray, especialment per a grans conjunts de dades. Tanmateix, s'han de tenir en compte les seves limitacions a l'hora d'utilitzar-lo per a aplicacions específiques.