L'algorithme de Kadane est une approche de programmation dynamique utilisée pour résoudre le problème du sous-tableau maximum, qui consiste à trouver le sous-tableau contigu avec la somme maximale dans un tableau de nombres. L'algorithme a été proposé par Jay Kadane en 1984 et a une complexité temporelle de O(n).
Historique de l'algorithme de Kadane :
L'algorithme de Kadane doit son nom à son inventeur, Jay Kadane, professeur d'informatique à l'université Carnegie Mellon. Il a décrit l'algorithme pour la première fois dans un article intitulé « Problème de sous-tableau à somme maximale » publié dans le Journal of the Association for Computing Machinery (ACM) en 1984.
Le problème de la recherche du sous-réseau maximum est étudié par les informaticiens depuis les années 1970. Il s'agit d'un problème bien connu dans le domaine de la conception et de l'analyse d'algorithmes et qui trouve des applications dans un large éventail de domaines, notamment le traitement du signal, la finance et la bioinformatique.
pente indéfinie
Avant l'algorithme de Kadane, d'autres algorithmes avaient été proposés pour résoudre le problème du sous-réseau maximum, comme l'approche par force brute qui vérifie tous les sous-réseaux possibles et l'algorithme diviser pour régner. Cependant, ces algorithmes ont des complexités temporelles plus élevées et sont moins efficaces que l'algorithme de Kadane.
L'algorithme de Kadane est largement utilisé en informatique et est devenu un exemple classique de programmation dynamique. Sa simplicité, son efficacité et son élégance en ont fait une solution populaire au problème du sous-réseau maximum et un outil précieux dans la conception et l'analyse d'algorithmes.
Fonctionnement de l'algorithme de Kadene :
L'algorithme fonctionne en itérant sur le tableau et en gardant une trace de la somme maximale du sous-tableau se terminant à chaque position. À chaque position i, nous avons deux options : soit ajouter l'élément à la position i au sous-tableau maximum actuel, soit démarrer un nouveau sous-tableau à la position i. Le maximum de ces deux options est le sous-réseau maximum se terminant à la position i.
Nous maintenons deux variables, max_so_far et max_ending_here, pour garder une trace de la somme maximale vue jusqu'à présent et de la somme maximale se terminant à la position actuelle, respectivement. L'algorithme commence par définir les deux variables sur le premier élément du tableau. Ensuite, nous parcourons le tableau du deuxième élément jusqu’à la fin.
A chaque position i, nous mettons à jour max_ending_here en prenant le maximum de l'élément actuel et l'élément actuel ajouté au sous-tableau maximum précédent. Nous mettons ensuite à jour max_so_far pour qu'il soit le maximum de max_so_far et max_ending_here.
L'algorithme renvoie max_so_far, qui est la somme maximale de n'importe quel sous-tableau du tableau.
Voici le processus étape par étape de l'algorithme de Kadane :
1. Initialisez deux variables, max_so_far et max_ending_here , au premier élément du tableau.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Parcourez le tableau du deuxième élément à la fin :
pour i de 1 à n-1 faire :
3. Calculez la somme maximale se terminant à la position actuelle :
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Mettez à jour max_so_far pour qu'il soit le maximum de max_so_far et max_ending_here :
max_so_far = max(max_so_far, max_ending_here)
5. Renvoyez max_so_far comme somme maximale de tout sous-tableau du tableau.
La complexité temporelle de l'algorithme de Kadane est O(n), où n est la longueur du tableau d'entrée. Cela en fait une solution très efficace au problème du sous-réseau maximum.
Exemple:
Voyons un exemple du fonctionnement de l'algorithme de Kadane :
Supposons que nous ayons le tableau d’entiers suivant :
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Nous voulons trouver la somme maximale des sous-tableaux de ce tableau. Nous pouvons appliquer l'algorithme de Kadane pour résoudre ce problème.
On commence par initialiser deux variables :
max_so_far = INT_MIN; max_ending_here = 0;
Ensuite, nous parcourons le tableau, en commençant par le deuxième élément :
for i in range(1, len(arr)):
Mettez à jour la somme actuelle en ajoutant l'élément actuel à la somme précédente :
max_ending_here = max(arr[i], max_ending_here + arr[i])
Mettez à jour la somme maximale vue jusqu'à présent :
max_so_far = max(max_so_far, max_ending_here)
À chaque itération, nous mettons à jour la somme actuelle en ajoutant l'élément actuel à la somme précédente ou en démarrant un nouveau sous-tableau au niveau de l'élément actuel. Nous mettons ensuite à jour la somme maximale observée jusqu'à présent en la comparant avec la somme actuelle.
Après avoir parcouru l'ensemble du tableau, la valeur de max_so_far sera la somme maximale des sous-tableaux du tableau donné.
Dans cet exemple, la somme maximale du sous-tableau est de 6, ce qui correspond au sous-tableau [4, -1, 2, 1].
Implémentation du code 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++){> Implémentation du code 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;> Avantages et inconvénients de l'algorithme de Kadane :
Avantages de l'algorithme de Kadane :
Inconvénients de l'algorithme de Kadane :
Applications de l'algorithme de Kadane :
Il existe certaines de ses applications comme les suivantes :
Par conséquent, nous pouvons dire que les avantages de l'algorithme de Kadane en font une excellente solution pour résoudre le problème du sous-tableau maximum, en particulier pour les grands ensembles de données. Cependant, ses limites doivent être prises en compte lors de son utilisation pour des applications spécifiques.