Kadanes algoritme er en dynamisk programmeringstilgang, der bruges til at løse det maksimale subarray-problem, som involverer at finde den sammenhængende subarray med den maksimale sum i en matrix af tal. Algoritmen blev foreslået af Jay Kadane i 1984 og har en tidskompleksitet på O(n).
Historien om Kadanes algoritme:
Kadanes algoritme er opkaldt efter dens opfinder, Jay Kadane, en professor i datalogi ved Carnegie Mellon University. Han beskrev først algoritmen i et papir med titlen 'Maximum Sum Subarray Problem' offentliggjort i Journal of the Association for Computing Machinery (ACM) i 1984.
Problemet med at finde den maksimale subarray er blevet undersøgt af dataloger siden 1970'erne. Det er et velkendt problem inden for algoritmedesign og analyse og har applikationer inden for en lang række områder, herunder signalbehandling, økonomi og bioinformatik.
java-streng af array
Forud for Kadanes algoritme var andre algoritmer blevet foreslået til at løse det maksimale subarray-problem, såsom brute-force-tilgangen, der tjekker alle mulige subarrays og divide-and-conquer-algoritmen. Disse algoritmer har dog højere tidskompleksiteter og er mindre effektive end Kadanes algoritme.
Kadanes algoritme er meget brugt i datalogi og er blevet et klassisk eksempel på dynamisk programmering. Dens enkelhed, effektivitet og elegance har gjort det til en populær løsning på det maksimale subarray-problem og et værdifuldt værktøj i algoritmedesign og analyse.
Kadenes algoritme fungerer:
Algoritmen fungerer ved at iterere over arrayet og holde styr på den maksimale sum af underarrayet, der slutter ved hver position. Ved hver position i har vi to muligheder: enten tilføje elementet i position i til den nuværende maksimale subarray eller starte en ny subarray på position i. Det maksimale af disse to muligheder er det maksimale underarray, der ender ved position i.
Vi opretholder to variabler, max_so_far og max_ending_here, for at holde styr på henholdsvis den maksimale sum set indtil nu og den maksimale sum der slutter på den aktuelle position. Algoritmen starter med at sætte begge variable til det første element i arrayet. Derefter itererer vi over arrayet fra det andet element til slutningen.
Ved hver position i opdaterer vi max_ending_here ved at tage maksimum af det aktuelle element og det aktuelle element tilføjet til det forrige maksimale underarray. Vi opdaterer derefter max_so_far til at være maksimum af max_so_far og max_ending_here.
Algoritmen returnerer max_so_far, som er den maksimale sum af enhver subarray i arrayet.
Her er trin-for-trin-processen af Kadanes algoritme:
1. Initialiser to variable, max_indtil videre og max_ending_her , til det første element i arrayet.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Iterér over arrayet fra det andet element til slutningen:
flette sorter i java
for i fra 1 til n-1 gør:
3. Beregn den maksimale sum, der slutter på den aktuelle position:
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Opdater max_so_far til at være maksimum af max_so_far og max_ending_here:
max_so_far = max(max_so_far, max_ending_here)
java sammenkædede strenge
5. Returner max_so_far som den maksimale sum af ethvert underarray i arrayet.
Tidskompleksiteten af Kadanes algoritme er O(n), hvor n er længden af input-arrayet. Dette gør det til en meget effektiv løsning på det maksimale subarray-problem.
Eksempel:
Lad os se et eksempel på, hvordan Kadanes algoritme virker:
Antag, at vi har følgende array af heltal:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Vi ønsker at finde den maksimale subarray sum af denne matrix. Vi kan anvende Kadanes algoritme til at løse dette problem.
Vi starter med at initialisere to variable:
max_so_far = INT_MIN; max_ending_here = 0;
Derefter itererer vi gennem arrayet, startende fra det andet element:
for i in range(1, len(arr)):
Opdater den aktuelle sum ved at tilføje det aktuelle element til den forrige sum:
array tilføjer elementer java
max_ending_here = max(arr[i], max_ending_here + arr[i])
Opdater den maksimale sum set indtil videre:
max_so_far = max(max_so_far, max_ending_here)
Ved hver iteration opdaterer vi den aktuelle sum ved enten at føje det aktuelle element til den forrige sum eller starte en ny subarray ved det aktuelle element. Vi opdaterer derefter den hidtil maksimale sum ved at sammenligne den med den aktuelle sum.
Efter iteration gennem hele arrayet vil værdien af max_so_far være den maksimale subarray-sum af det givne array.
I dette eksempel er den maksimale subarray-sum 6, hvilket svarer til subarrayet [4, -1, 2, 1].
Kodeimplementering i 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++){> Kodeimplementering i 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;> Fordele og ulemper ved Kadanes algoritme:
Fordele ved Kadanes algoritme:
Ulemper ved Kadanes algoritme:
Anvendelser af Kadanes algoritme:
Der er nogle af dens applikationer som følgende:
Derfor kan vi sige, at fordelene ved Kadanes algoritme gør det til en fantastisk løsning til at løse det maksimale subarray-problem, især for store datasæt. Dets begrænsninger skal dog tages i betragtning, når det bruges til specifikke applikationer.