Kadane의 알고리즘은 숫자 배열에서 최대 합을 갖는 연속 하위 배열을 찾는 것과 관련된 최대 하위 배열 문제를 해결하는 데 사용되는 동적 프로그래밍 접근 방식입니다. 이 알고리즘은 1984년 Jay Kadane에 의해 제안되었으며 O(n)의 시간 복잡도를 갖습니다.
Kadane 알고리즘의 역사:
Kadane의 알고리즘은 이를 발명한 Carnegie Mellon University의 컴퓨터 과학 교수인 Jay Kadane의 이름을 따서 명명되었습니다. 그는 1984년 Journal of the Association for Computing Machinery(ACM)에 게재된 'Maximum Sum Subarray Problem'이라는 제목의 논문에서 알고리즘을 처음 설명했습니다.
최대 부분배열을 찾는 문제는 1970년대부터 컴퓨터 과학자들에 의해 연구되어 왔습니다. 알고리즘 설계 및 분석 분야에서 잘 알려진 문제로 신호처리, 금융, 생물정보학 등 폭넓은 분야에 응용되고 있습니다.
구별되게 세다
Kadane의 알고리즘 이전에는 최대 하위 배열 문제를 해결하기 위해 가능한 모든 하위 배열을 확인하는 무차별 접근 방식 및 분할 정복 알고리즘과 같은 다른 알고리즘이 제안되었습니다. 그러나 이러한 알고리즘은 Kadane의 알고리즘보다 시간 복잡도가 높고 효율성이 떨어집니다.
Kadane의 알고리즘은 컴퓨터 과학에서 널리 사용되며 동적 프로그래밍의 전형적인 예가 되었습니다. 단순성, 효율성 및 우아함 덕분에 최대 하위 배열 문제에 대한 인기 있는 솔루션이자 알고리즘 설계 및 분석에서 귀중한 도구가 되었습니다.
Kadene 알고리즘의 작동:
알고리즘은 배열을 반복하고 각 위치에서 끝나는 하위 배열의 최대 합계를 추적하는 방식으로 작동합니다. 각 위치 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. 두 번째 요소부터 끝까지 배열을 반복합니다.
1에서 n-1까지의 i에 대해 다음을 수행하십시오.
자식 상태 -s
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_so_far, max_ending_here)
5. 배열에 있는 하위 배열의 최대 합계로 max_so_far를 반환합니다.
Kadane 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 입력 배열의 길이입니다. 이는 최대 하위 배열 문제에 대한 매우 효율적인 솔루션이 됩니다.
예:
Kadane의 알고리즘이 어떻게 작동하는지 예를 살펴보겠습니다.
다음과 같은 정수 배열이 있다고 가정합니다.
스프링 부트 주석
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
우리는 이 배열의 최대 하위 배열 합계를 찾고 싶습니다. 이 문제를 해결하기 위해 Kadane의 알고리즘을 적용할 수 있습니다.
두 가지 변수를 초기화하는 것부터 시작합니다.
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]에 해당합니다.
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 알고리즘의 장점과 단점:
Kadane 알고리즘의 장점:
Kadane 알고리즘의 단점:
Kadane 알고리즘의 응용:
다음과 같은 일부 응용 프로그램이 있습니다.
따라서 Kadane 알고리즘의 장점은 특히 대규모 데이터 세트의 경우 최대 하위 배열 문제를 해결하는 데 훌륭한 솔루션이라고 말할 수 있습니다. 그러나 특정 응용 프로그램에 사용할 때는 제한 사항을 고려해야 합니다.