Каданеов алгоритам је динамички програмски приступ који се користи за решавање проблема максималног подниза, који укључује проналажење суседног подниза са максималним сумом у низу бројева. Алгоритам је предложио Јаи Кадане 1984. године и има временску сложеност од О(н).
Историја Каданеовог алгоритма:
Каданеов алгоритам је назван по свом проналазачу, Џеју Каданеу, професору рачунарских наука на Универзитету Карнеги Мелон. Он је први пут описао алгоритам у раду под насловом „Проблем са максималном сумом подбара“ објављеном у часопису Удружења за рачунарске машине (АЦМ) 1984. године.
Проблем проналажења максималног подниза проучавали су компјутерски научници од 1970-их. То је добро познат проблем у области пројектовања и анализе алгоритама и има примену у широком спектру области, укључујући обраду сигнала, финансије и биоинформатику.
цсс бацкгроунд
Пре Каданеовог алгоритма, други алгоритми су били предложени за решавање проблема максималног подниза, као што је приступ грубе силе који проверава све могуће поднизе и алгоритам завади и владај. Међутим, ови алгоритми имају већу временску сложеност и мање су ефикасни од Каданеовог алгоритма.
Каданеов алгоритам се широко користи у рачунарству и постао је класичан пример динамичког програмирања. Његова једноставност, ефикасност и елеганција учинили су га популарним решењем за проблем максималног подниза и вредним алатом у дизајну и анализи алгоритама.
Рад Кадениног алгоритма:
Алгоритам функционише тако што се понавља низ низ и прати максималан збир подниза који се завршава на свакој позицији. На свакој позицији и, имамо две опције: или додати елемент на позицији и тренутном максималном поднису или започети нови подниз на позицији и. Максимум од ове две опције је максимални подниз који се завршава на позицији и.
Одржавамо две променљиве, мак_со_фар и мак_ендинг_хере, да бисмо пратили максималну суму виђену до сада и максималну суму која се завршава на тренутној позицији, респективно. Алгоритам почиње постављањем обе променљиве на први елемент низа. Затим прелазимо низ низ од другог елемента до краја.
На свакој позицији и, ажурирамо мак_ендинг_хере узимајући максимум тренутног елемента и тренутног елемента доданог претходном максималном поднису. Затим ажурирамо мак_со_фар да буде максимум мак_со_фар и мак_ендинг_хере.
Алгоритам враћа мак_со_фар, што је максимални збир било ког подниза у низу.
Ево корак по корак процеса Каданеовог алгоритма:
1. Иницијализујте две променљиве, мак_со_фар и мак_ендинг_хере , до првог елемента низа.
мак_со_фар = арр[0]
мак_ендинг_хере = арр[0]
2. Итерирајте низ од другог елемента до краја:
за и од 1 до н-1 урадите:
3. Израчунајте максималну суму која се завршава на тренутној позицији:
јава је инстанцеоф
мак_ендинг_хере = мак(арр[и], мак_ендинг_хере + арр[и])
4. Ажурирајте мак_со_фар да буде максимум мак_со_фар и мак_ендинг_овде:
мак_со_фар = мак(мак_со_фар, мак_ендинг_овде)
5. Врати мак_со_фар као максималан збир било ког подниза у низу.
Временска сложеност Каданеовог алгоритма је О(н), где је н дужина улазног низа. Ово га чини веома ефикасним решењем за проблем максималног подниза.
Пример:
Хајде да видимо на примеру како функционише Каданеов алгоритам:
Претпоставимо да имамо следећи низ целих бројева:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Желимо да пронађемо максималну суму подниза овог низа. Можемо применити Каданеов алгоритам да решимо овај проблем.
Почињемо са иницијализацијом две променљиве:
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)
На свакој итерацији ажурирамо тренутни збир додавањем тренутног елемента претходном збиру или покретањем новог подниза на тренутном елементу. Затим ажурирамо максималну суму која је до сада виђена упоређујући је са тренутном сумом.
Након итерације кроз цео низ, вредност мак_со_фар ће бити максимални збир подниза датог низа.
У овом примеру, максимални збир подниза је 6, што одговара поднизу [4, -1, 2, 1].
јава упореди стрингове
Имплементација кода у Јави:
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++){> Имплементација кода у Ц++:
#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;> Предности и недостаци Каданеовог алгоритма:
Предности Каданеовог алгоритма:
Недостаци Каданеовог алгоритма:
Примене Каданеовог алгоритма:
Постоје неке од његових апликација као што су следеће:
Стога, можемо рећи да предности Каданеовог алгоритма чине га одличним решењем за решавање проблема максималног подниза, посебно за велике скупове података. Међутим, морају се узети у обзир његова ограничења када се користи за специфичне апликације.