Kadaneov algoritam je pristup dinamičkom programiranju koji se koristi za rješavanje problema maksimalnog podniza, koji uključuje pronalaženje susjednog podniza s maksimalnim zbrojem u nizu brojeva. Algoritam je predložio Jay Kadane 1984. i ima vremensku složenost O(n).
Povijest Kadaneovog algoritma:
Kadaneov algoritam nazvan je po svom izumitelju, Jayu Kadaneu, profesoru informatike na Sveučilištu Carnegie Mellon. Prvi put je opisao algoritam u radu pod naslovom 'Maximum Sum Subarray Problem' objavljenom u Journal of Association for Computing Machinery (ACM) 1984. godine.
Problem pronalaženja maksimalnog podniza proučavaju računalni znanstvenici od 1970-ih. To je dobro poznat problem u području dizajna i analize algoritama i ima primjenu u širokom rasponu područja, uključujući obradu signala, financije i bioinformatiku.
Prije Kadaneovog algoritma, predlagani su drugi algoritmi za rješavanje problema maksimalnog podniza, kao što je pristup brutalnom silom koji provjerava sve moguće podnizove i algoritam podijeli i vladaj. Međutim, ti algoritmi imaju veću vremensku složenost i manje su učinkoviti od Kadaneovog algoritma.
Kadaneov algoritam naširoko se koristi u računalnoj znanosti i postao je klasičan primjer dinamičkog programiranja. Njegova jednostavnost, učinkovitost i elegancija učinile su ga popularnim rješenjem za problem maksimalne podmarice i vrijednim alatom u dizajnu i analizi algoritama.
Rad Kadeneovog algoritma:
Algoritam radi iteracijom preko niza i praćenjem maksimalnog zbroja podniza koji završava na svakoj poziciji. Na svakoj poziciji i imamo dvije mogućnosti: dodati element na poziciji i trenutnoj maksimalnoj podnizu ili započeti novu podnizu na poziciji i. Maksimum od ove dvije opcije je maksimalni podniz koji završava na poziciji i.
Održavamo dvije varijable, max_so_far i max_ending_here, kako bismo pratili maksimalni zbroj viđen do sada, odnosno maksimalni zbroj koji završava na trenutnoj poziciji. Algoritam počinje postavljanjem obje varijable na prvi element niza. Zatim iteriramo po nizu od drugog elementa do kraja.
Na svakoj poziciji i ažuriramo max_ending_here uzimajući maksimum trenutnog elementa i trenutni element dodan prethodnom maksimalnom podnizu. Zatim ažuriramo max_so_far da bude maksimum max_so_far i max_ending_here.
poredak slučajnim sql-om
Algoritam vraća max_so_far, što je najveći zbroj bilo kojeg podniza u nizu.
Evo procesa Kadaneovog algoritma korak po korak:
1. Inicijalizirajte dvije varijable, max_so_daleko i maksimalni_završetak_ovdje , na prvi element niza.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Iterirajte preko niza od drugog elementa do kraja:
za i od 1 do n-1 napravite:
3. Izračunajte najveći zbroj koji završava na trenutnoj poziciji:
topologija mreže
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Ažurirajte max_so_far da bude maksimum max_so_far i max_ending_here:
max_so_daleko = max(max_so_daleko, max_ending_here)
5. Vrati max_so_far kao najveći zbroj bilo kojeg podniza u nizu.
Vremenska složenost Kadaneovog algoritma je O(n), gdje je n duljina ulaznog niza. To ga čini vrlo učinkovitim rješenjem problema maksimalnog podniza.
Primjer:
Pogledajmo na primjeru kako radi Kadaneov algoritam:
Pretpostavimo da imamo sljedeći niz cijelih brojeva:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Želimo pronaći maksimalnu sumu podniza ovog niza. Za rješavanje ovog problema možemo primijeniti Kadaneov algoritam.
Počinjemo inicijalizacijom dvije varijable:
max_so_far = INT_MIN; max_ending_here = 0;
Zatim ponavljamo kroz niz, počevši od drugog elementa:
10 od 50,00 kn
for i in range(1, len(arr)):
Ažurirajte trenutni zbroj dodavanjem trenutnog elementa prethodnom zbroju:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Ažurirajte do sada najveći zbroj:
max_so_far = max(max_so_far, max_ending_here)
U svakoj iteraciji ažuriramo trenutni zbroj ili dodavanjem trenutnog elementa prethodnom zbroju ili pokretanjem novog podniza na trenutnom elementu. Zatim ažuriramo najveći do sada viđeni zbroj uspoređujući ga s trenutnim zbrojem.
Nakon ponavljanja kroz cijeli niz, vrijednost max_so_far bit će maksimalni zbroj podniza zadanog niza.
U ovom primjeru maksimalni zbroj podniza je 6, što odgovara podnizu [4, -1, 2, 1].
Implementacija koda u Javi:
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++){> Implementacija koda u 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;> Prednosti i nedostaci Kadaneovog algoritma:
Prednosti Kadaneovog algoritma:
Nedostaci Kadaneovog algoritma:
Primjene Kadaneovog algoritma:
Postoje neke od njegovih primjena poput sljedećih:
Stoga možemo reći da prednosti Kadaneovog algoritma čine izvrsnim rješenjem za rješavanje problema maksimalnog podniza, posebno za velike skupove podataka. Međutim, njegova ograničenja moraju se uzeti u obzir kada se koristi za određene primjene.