Kadanes algoritme er en dynamisk programmeringstilnærming som brukes for å løse det maksimale subarray-problemet, som innebærer å finne den sammenhengende subarrayen med maksimal sum i en matrise med tall. Algoritmen ble foreslått av Jay Kadane i 1984 og har en tidskompleksitet på O(n).
Historien om Kadanes algoritme:
Kadanes algoritme er oppkalt etter oppfinneren, Jay Kadane, en informatikkprofessor ved Carnegie Mellon University. Han beskrev først algoritmen i en artikkel med tittelen 'Maximum Sum Subarray Problem' publisert i Journal of the Association for Computing Machinery (ACM) i 1984.
Problemet med å finne den maksimale undergruppen har blitt studert av dataforskere siden 1970-tallet. Det er et velkjent problem innen algoritmedesign og -analyse og har applikasjoner innen et bredt spekter av områder, inkludert signalbehandling, økonomi og bioinformatikk.
java-streng av array
Før Kadanes algoritme hadde andre algoritmer blitt foreslått for å løse det maksimale subarray-problemet, for eksempel brute-force-tilnærmingen som sjekker alle mulige subarrays og divide-and-conquer-algoritmen. Imidlertid har disse algoritmene høyere tidskompleksitet og er mindre effektive enn Kadanes algoritme.
Kadanes algoritme er mye brukt i informatikk og har blitt et klassisk eksempel på dynamisk programmering. Dens enkelhet, effektivitet og eleganse har gjort det til en populær løsning på det maksimale subarray-problemet og et verdifullt verktøy i algoritmedesign og analyse.
Arbeidet med Kadenes algoritme:
Algoritmen fungerer ved å iterere over matrisen og holde styr på den maksimale summen av subarrayen som slutter ved hver posisjon. Ved hver posisjon i har vi to alternativer: enten legge til elementet i posisjon i til den nåværende maksimale undergruppen eller starte en ny undergruppe ved posisjon i. Det maksimale av disse to alternativene er den maksimale undergruppen som slutter ved posisjon i.
Vi opprettholder to variabler, max_so_far og max_ending_here, for å holde styr på henholdsvis den maksimale summen sett så langt og den maksimale summen som slutter på gjeldende posisjon. Algoritmen starter med å sette begge variablene til det første elementet i matrisen. Deretter itererer vi over matrisen fra det andre elementet til slutten.
Ved hver posisjon i oppdaterer vi max_ending_here ved å ta maksimum av det gjeldende elementet og det nåværende elementet lagt til den forrige maksimale undergruppen. Vi oppdaterer så max_so_far til å være maksimum av max_so_far og max_ending_here.
Algoritmen returnerer max_so_far, som er den maksimale summen av en hvilken som helst delmatrise i matrisen.
Her er trinn-for-trinn-prosessen til Kadanes algoritme:
1. Initialiser to variabler, maks_så_langt og maks_ending_her , til det første elementet i matrisen.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Iterer over matrisen fra det andre elementet til slutten:
slå sammen sortering i java
for i fra 1 til n-1 gjør:
3. Beregn den maksimale summen som slutter på gjeldende posisjon:
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Oppdater max_so_far til å være maksimum av max_so_far og max_ending_here:
max_so_far = max(max_so_far, max_ending_here)
java sammenknytte strenger
5. Returner max_so_far som den maksimale summen av en undermatrise i matrisen.
Tidskompleksiteten til Kadanes algoritme er O(n), der n er lengden på inngangsmatrisen. Dette gjør det til en veldig effektiv løsning på det maksimale subarray-problemet.
Eksempel:
La oss se på et eksempel på hvordan Kadanes algoritme fungerer:
Anta at vi har følgende rekke med heltall:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Vi ønsker å finne den maksimale subarray summen av denne matrisen. Vi kan bruke Kadanes algoritme for å løse dette problemet.
Vi starter med å initialisere to variabler:
max_so_far = INT_MIN; max_ending_here = 0;
Deretter itererer vi gjennom matrisen, fra det andre elementet:
for i in range(1, len(arr)):
Oppdater gjeldende sum ved å legge til gjeldende element til forrige sum:
primærnøkkel og sammensatt nøkkel i sql
max_ending_here = max(arr[i], max_ending_here + arr[i])
Oppdater den maksimale summen som er sett så langt:
max_so_far = max(max_so_far, max_ending_here)
Ved hver iterasjon oppdaterer vi den gjeldende summen ved enten å legge det gjeldende elementet til den forrige summen eller starte en ny undergruppe ved det gjeldende elementet. Vi oppdaterer så den maksimale summen sett så langt ved å sammenligne den med gjeldende sum.
Etter å ha iterert gjennom hele matrisen, vil verdien av max_so_far være den maksimale submatrisesummen av den gitte matrisen.
I dette eksemplet er den maksimale subarray-summen 6, som tilsvarer subarrayen [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;> Fordeler og ulemper med Kadanes algoritme:
Fordeler med Kadanes algoritme:
Ulemper med Kadanes algoritme:
Anvendelser av Kadanes algoritme:
Det er noen av dens applikasjoner som følgende:
Derfor kan vi si at fordelene med Kadanes algoritme gjør den til en flott løsning for å løse det maksimale subarray-problemet, spesielt for store datasett. Begrensningene må imidlertid vurderes når du bruker den til spesifikke applikasjoner.