Algorytm Kadane'a to podejście do programowania dynamicznego stosowane do rozwiązywania problemu maksymalnej podtablicy, który polega na znalezieniu ciągłej podtablicy z maksymalną sumą w tablicy liczb. Algorytm został zaproponowany przez Jaya Kadane'a w 1984 roku i ma złożoność czasową O(n).
Historia algorytmu Kadane’a:
Algorytm Kadane został nazwany na cześć jego wynalazcy, Jaya Kadane’a, profesora informatyki na Uniwersytecie Carnegie Mellon. Po raz pierwszy opisał algorytm w artykule zatytułowanym „Problem podtablicy maksymalnej sumy” opublikowanym w czasopiśmie Journal of Association for Computing Machinery (ACM) w 1984 r.
Problemem znalezienia maksymalnej podtablicy zajmują się informatycy od lat 70. XX wieku. Jest to dobrze znany problem w dziedzinie projektowania i analizy algorytmów i ma zastosowanie w wielu obszarach, w tym w przetwarzaniu sygnałów, finansach i bioinformatyce.
metody Javy
Przed algorytmem Kadane'a proponowano inne algorytmy rozwiązywania problemu maksymalnej podtablicy, takie jak podejście brute-force, które sprawdza wszystkie możliwe podtablice oraz algorytm dziel i zwyciężaj. Algorytmy te mają jednak większą złożoność czasową i są mniej wydajne niż algorytm Kadane’a.
Algorytm Kadane'a jest szeroko stosowany w informatyce i stał się klasycznym przykładem programowania dynamicznego. Jego prostota, wydajność i elegancja uczyniły z niego popularne rozwiązanie problemu maksymalnej podtablicy oraz cenne narzędzie w projektowaniu i analizie algorytmów.
Działanie algorytmu Kadene’a:
Algorytm działa poprzez iterację po tablicy i śledzenie maksymalnej sumy podtablicy kończącej się na każdej pozycji. Dla każdej pozycji i mamy dwie możliwości: albo dodać element na pozycji i do aktualnej maksymalnej podtablicy, albo rozpocząć nową podtablicę na pozycji i. Maksymalna z tych dwóch opcji jest maksymalną podtablicą kończącą się na pozycji i.
Utrzymujemy dwie zmienne, max_so_far i max_ending_here, aby śledzić odpowiednio maksymalną sumę widzianą do tej pory i maksymalną sumę kończącą się na bieżącej pozycji. Algorytm rozpoczyna się od ustawienia obu zmiennych na pierwszy element tablicy. Następnie iterujemy po tablicy od drugiego elementu do końca.
W każdej pozycji i aktualizujemy max_ending_here, biorąc maksimum bieżącego elementu i bieżący element dodany do poprzedniej podtablicy maksimum. Następnie aktualizujemy max_so_far tak, aby było maksimum max_so_far i max_ending_here.
Algorytm zwraca max_so_far, który jest maksymalną sumą dowolnej podtablicy w tablicy.
Oto krok po kroku proces algorytmu Kadane'a:
1. Zainicjuj dwie zmienne, max_so_far I max_ending_tutaj , do pierwszego elementu tablicy.
max_so_far = tablica[0]
max_ending_here = tablica[0]
2. Iteruj po tablicy od drugiego elementu do końca:
dla i od 1 do n-1 wykonaj:
3. Oblicz maksymalną sumę kończącą się na bieżącej pozycji:
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Zaktualizuj max_so_far na maksimum max_so_far i max_ending_here:
max_so_far = max(max_so_far, max_ending_here)
5. Zwróć max_so_far jako maksymalną sumę dowolnej podtablicy w tablicy.
Złożoność czasowa algorytmu Kadane’a wynosi O(n), gdzie n jest długością tablicy wejściowej. To sprawia, że jest to bardzo wydajne rozwiązanie problemu maksymalnej podtablicy.
Przykład:
Zobaczmy na przykładzie działania algorytmu Kadane’a:
Załóżmy, że mamy następującą tablicę liczb całkowitych:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Chcemy znaleźć maksymalną sumę podtablicy tej tablicy. Do rozwiązania tego problemu możemy zastosować algorytm Kadane’a.
Zaczynamy od inicjalizacji dwóch zmiennych:
max_so_far = INT_MIN; max_ending_here = 0;
Następnie iterujemy po tablicy, zaczynając od drugiego elementu:
for i in range(1, len(arr)):
Zaktualizuj bieżącą sumę, dodając bieżący element do poprzedniej sumy:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Zaktualizuj maksymalną kwotę zaobserwowaną do tej pory:
max_so_far = max(max_so_far, max_ending_here)
Przy każdej iteracji aktualizujemy bieżącą sumę, dodając bieżący element do poprzedniej sumy lub rozpoczynając nową podtablicę od bieżącego elementu. Następnie aktualizujemy maksymalną sumę zaobserwowaną do tej pory, porównując ją z sumą bieżącą.
Po iteracji po całej tablicy wartość max_so_far będzie maksymalną sumą podtablicy danej tablicy.
W tym przykładzie maksymalna suma podtablicy wynosi 6, co odpowiada podtablicy [4, -1, 2, 1].
Implementacja kodu w Javie:
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++){> Implementacja kodu w 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;> Zalety i wady algorytmu Kadane’a:
Zalety algorytmu Kadane’a:
Wady algorytmu Kadane’a:
Zastosowania algorytmu Kadane’a:
Istnieje kilka jego zastosowań, takich jak następujące:
Dlatego możemy powiedzieć, że zalety algorytmu Kadane’a sprawiają, że jest on doskonałym rozwiązaniem do rozwiązywania problemu maksymalnej podtablicy, szczególnie w przypadku dużych zbiorów danych. Używając go do konkretnych zastosowań, należy jednak wziąć pod uwagę jego ograniczenia.