Алгоритъмът на Kadane е подход за динамично програмиране, използван за решаване на проблема с максималния подмасив, който включва намиране на съседния подмасив с максималната сума в масив от числа. Алгоритъмът е предложен от Jay Kadane през 1984 г. и има времева сложност O(n).
срез на java масив
История на алгоритъма на Кадан:
Алгоритъмът на Kadane е кръстен на своя изобретател, Джей Kadane, професор по компютърни науки в университета Carnegie Mellon. Той за първи път описва алгоритъма в статия, озаглавена „Проблем с максимален сбор на подмасиви“, публикувана в Journal of Association for Computing Machinery (ACM) през 1984 г.
Проблемът с намирането на максималния подмасив се изучава от компютърни учени от 1970 г. насам. Това е добре известен проблем в областта на дизайна и анализа на алгоритми и има приложения в широк спектър от области, включително обработка на сигнали, финанси и биоинформатика.
Преди алгоритъма на Кадане бяха предложени други алгоритми за решаване на проблема с максималния подмасив, като подхода с груба сила, който проверява всички възможни подмасиви и алгоритъма разделяй и владей. Въпреки това, тези алгоритми имат по-висока времева сложност и са по-малко ефективни от алгоритъма на Kadane.
Алгоритъмът на Кадане се използва широко в компютърните науки и се превърна в класически пример за динамично програмиране. Неговата простота, ефективност и елегантност го превърнаха в популярно решение на проблема с максималния подмасив и ценен инструмент при проектиране и анализ на алгоритми.
Работа на алгоритъма на Каден:
Алгоритъмът работи, като итерира масива и следи максималната сума на подмасива, завършваща на всяка позиция. Във всяка позиция i имаме две възможности: или да добавим елемента на позиция i към текущия максимален подмасив, или да започнем нов подмасив на позиция i. Максимумът от тези две опции е максималният подмасив, завършващ на позиция i.
Поддържаме две променливи, max_so_far и max_ending_here, за да следим съответно максималната сума, наблюдавана до момента, и максималната сума, завършваща на текущата позиция. Алгоритъмът започва със задаване на двете променливи на първия елемент от масива. След това итерираме масива от втория елемент до края.
На всяка позиция i актуализираме max_ending_here, като вземем максимума от текущия елемент и текущия елемент, добавен към предишния максимален подмасив. След това актуализираме max_so_far, за да бъде максимумът на max_so_far и max_ending_here.
Алгоритъмът връща max_so_far, което е максималната сума на всеки подмасив в масива.
Ето процеса стъпка по стъпка на алгоритъма на Kadane:
1. Инициализирайте две променливи, max_so_far и макс_край_тук , към първия елемент от масива.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Обходете масива от втория елемент до края:
капсулиране в java
за i от 1 до n-1 направете:
3. Изчислете максималната сума, завършваща на текущата позиция:
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Актуализирайте max_so_far, за да бъде максимумът на max_so_far и max_ending_here:
max_so_far = max(max_so_far, max_ending_here)
5. Връща max_so_far като максималната сума на всеки подмасив в масива.
Времевата сложност на алгоритъма на Kadane е O(n), където n е дължината на входния масив. Това го прави много ефективно решение на проблема с максималния подмасив.
Пример:
Нека да видим пример за това как работи алгоритъмът на Kadane:
Да предположим, че имаме следния масив от цели числа:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Искаме да намерим максималната сума на подмасива на този масив. Можем да приложим алгоритъма на Кадане, за да решим този проблем.
Започваме с инициализиране на две променливи:
как да промените низ на int
max_so_far = INT_MIN; max_ending_here = 0;
След това преминаваме през масива, започвайки от втория елемент:
for i in range(1, len(arr)):
Актуализирайте текущата сума, като добавите текущия елемент към предишната сума:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Актуализирайте максималната сума, видяна досега:
max_so_far = max(max_so_far, max_ending_here)
При всяка итерация актуализираме текущата сума, като добавяме текущия елемент към предишната сума или започваме нов подмасив от текущия елемент. След това актуализираме максималната сума, наблюдавана досега, като я сравняваме с текущата сума.
След итерация през целия масив, стойността на max_so_far ще бъде максималната сума на подмасива на дадения масив.
В този пример максималната сума на подмасива е 6, което съответства на подмасива [4, -1, 2, 1].
aws червено отместване
Внедряване на код в 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++){> Внедряване на код в 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;> Предимства и недостатъци на алгоритъма на Кадан:
Предимства на алгоритъма на Кадан:
Недостатъци на алгоритъма на Кадан:
Приложения на алгоритъма на Кадан:
Има някои от неговите приложения като следното:
Следователно можем да кажем, че предимствата на алгоритъма на Kadane го правят чудесно решение за решаване на проблема с максималния подмасив, особено за големи набори от данни. Въпреки това, неговите ограничения трябва да се имат предвид, когато се използва за конкретни приложения.