Het algoritme van Kadane is een dynamische programmeerbenadering die wordt gebruikt om het probleem van de maximale subarray op te lossen, waarbij de aaneengesloten subarray wordt gevonden met de maximale som in een array van getallen. Het algoritme werd in 1984 voorgesteld door Jay Kadane en heeft een tijdscomplexiteit van O(n).
Geschiedenis van het algoritme van Kadane:
Het algoritme van Kadane is vernoemd naar de uitvinder, Jay Kadane, hoogleraar computerwetenschappen aan de Carnegie Mellon University. Hij beschreef het algoritme voor het eerst in een artikel met de titel 'Maximum Sum Subarray Problem', gepubliceerd in het Journal of the Association for Computing Machinery (ACM) in 1984.
Het probleem van het vinden van de maximale subarray wordt sinds de jaren zeventig door computerwetenschappers bestudeerd. Het is een bekend probleem op het gebied van algoritmeontwerp en -analyse en heeft toepassingen op een groot aantal gebieden, waaronder signaalverwerking, financiën en bio-informatica.
log4j
Vóór het algoritme van Kadane waren er andere algoritmen voorgesteld om het maximale subarray-probleem op te lossen, zoals de brute-force-benadering die alle mogelijke subarrays controleert en het verdeel-en-heers-algoritme. Deze algoritmen hebben echter een hogere tijdscomplexiteit en zijn minder efficiënt dan het algoritme van Kadane.
Het algoritme van Kadane wordt veel gebruikt in de informatica en is een klassiek voorbeeld van dynamisch programmeren geworden. Door zijn eenvoud, efficiëntie en elegantie is het een populaire oplossing geworden voor het maximale subarray-probleem en een waardevol hulpmiddel bij het ontwerpen en analyseren van algoritmen.
Werking van Kadene's algoritme:
Het algoritme werkt door de array te herhalen en de maximale som van de subarray die op elke positie eindigt bij te houden. Op elke positie i hebben we twee opties: voeg het element op positie i toe aan de huidige maximale subarray of start een nieuwe subarray op positie i. Het maximum van deze twee opties is de maximale subarray die eindigt op positie i.
We onderhouden twee variabelen, max_so_far en max_ending_here, om respectievelijk de maximale som die tot nu toe is gezien en de maximale som die eindigt op de huidige positie bij te houden. Het algoritme begint door beide variabelen in te stellen op het eerste element van de array. Vervolgens herhalen we de array vanaf het tweede element tot het einde.
pawandep rajan
Op elke positie i werken we max_ending_here bij door het maximum van het huidige element te nemen en het huidige element toegevoegd aan de vorige maximale subarray. Vervolgens werken we max_so_far bij tot het maximum van max_so_far en max_ending_here.
Het algoritme retourneert max_so_far, wat de maximale som is van elke subarray in de array.
Hier is het stapsgewijze proces van Kadane's algoritme:
1. Initialiseer twee variabelen, max_so_far En max_ending_hier , naar het eerste element van de array.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Herhaal de array vanaf het tweede element tot het einde:
voor i van 1 tot n-1 doe:
sites zoals bedpage
3. Bereken het maximale bedrag dat eindigt op de huidige positie:
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Update max_so_far zodat het het maximum is van max_so_far en max_ending_here:
max_so_far = max(max_so_far, max_ending_hier)
5. Geef max_so_far terug als de maximale som van elke subarray in de array.
De tijdscomplexiteit van het algoritme van Kadane is O(n), waarbij n de lengte van de invoerarray is. Dit maakt het een zeer efficiënte oplossing voor het maximale subarray-probleem.
Voorbeeld:
Laten we eens kijken naar een voorbeeld van hoe het algoritme van Kadane werkt:
Stel dat we de volgende reeks gehele getallen hebben:
datumtekenreeks java
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
We willen de maximale subarraysom van deze array vinden. We kunnen het algoritme van Kadane toepassen om dit probleem op te lossen.
We beginnen met het initialiseren van twee variabelen:
max_so_far = INT_MIN; max_ending_here = 0;
Vervolgens doorlopen we de array, beginnend bij het tweede element:
kandidaat sleutel
for i in range(1, len(arr)):
Werk de huidige som bij door het huidige element toe te voegen aan de vorige som:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Update het maximale bedrag dat tot nu toe is gezien:
max_so_far = max(max_so_far, max_ending_here)
Bij elke iteratie werken we de huidige som bij door het huidige element toe te voegen aan de vorige som of door een nieuwe subarray te starten bij het huidige element. Vervolgens werken we het maximale bedrag tot nu toe bij door het te vergelijken met het huidige bedrag.
Na het doorlopen van de gehele array zal de waarde van max_so_far de maximale subarraysom van de gegeven array zijn.
In dit voorbeeld is de maximale subarraysom 6, wat overeenkomt met de subarray [4, -1, 2, 1].
Code-implementatie in 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++){> Code-implementatie in 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;> Voor- en nadelen van Kadane's algoritme:
Voordelen van het Kadane-algoritme:
Nadelen van Kadane's algoritme:
Toepassingen van Kadane's algoritme:
Er zijn enkele van de toepassingen, zoals de volgende:
Daarom kunnen we zeggen dat de voordelen van Kadane's algoritme het een geweldige oplossing maken voor het oplossen van het maximale subarray-probleem, vooral voor grote datasets. Bij gebruik voor specifieke toepassingen moet echter rekening worden gehouden met de beperkingen ervan.