Kadence의 알고리즘: 최대 합 연속 하위 배열
사라 첸
⚡ 스마트 요약
카데인 알고리즘은 선형 시간 안에 가장 큰 합을 갖는 연속 부분 배열을 찾습니다. trac모든 가능한 부분 배열을 스캔하는 대신 최대값을 찾는 것이 더 효율적입니다. 이 고전적인 동적 프로그래밍 기법은 주식, 금융 및 신호 처리 문제에 적용됩니다.
연속된 부분 배열 중 가장 큰 합은 무엇입니까?
하위 배열은 배열의 연속적인 부분입니다. 배열의 단일 요소일 수도 있고 배열의 일부일 수도 있습니다. 합이 가장 큰 연속 부분배열은 합이 최대인 부분배열을 의미한다.
예를 들어, 배열 {-10, 5, 1, 6, -9, 2, -7, 3, -5}를 생각해 보세요. 이 배열의 부분 배열은 {-10, 5, 1, 6}, {5, 1, 6}, {2, -7, 3, -5} 등이 될 수 있습니다. 하지만 {5, 1, 6, 3}은 요소들이 연속된 순서가 아니므로 부분 배열이 될 수 없습니다.
자세히 보시면, 모든 부분 배열 중에서 강조 표시된 부분 배열 {5, 1, 6}의 합이 가장 큽니다.
부분 배열 {5, 1, 6}의 합은 12이며, 이는 위 배열의 모든 가능한 부분 배열 중에서 합이 가장 큰 값입니다. 따라서 이 배열에서 연속된 부분 배열 중 합이 가장 큰 것은 {5, 1, 6}입니다.
연속 부분 배열에서 최대 합을 구하는 간단한 방법
이 문제를 해결하는 간단한 방법은 두 개의 루프를 사용하여 모든 하위 배열을 찾고 합계를 계산한 다음 최대값을 찾는 것입니다.
다음은 연속된 부분 배열 중 가장 큰 합을 찾는 간단한 접근 방식의 순서도입니다. 이는 모든 가능한 부분 배열을 살펴보는 무차별 대입 방식입니다.
이를 수행하는 간단한 단계는 다음과 같습니다.
단계 1) 초기화 최대합 최소 정수 값을 사용하여 설정합니다. 시작하다 end XNUMX으로.
단계 2) 하자 i j 배열 인덱스가 됩니다. j 보다 크거나 같음 i; i 부분 배열의 시작을 표시합니다. j 그것의 끝.
단계 3) 현재 합계 누적 합계를 저장합니다. 각 업데이트 후, 다음을 확인합니다. 현재 합계 보다 큰 최대합.
단계 4) If 현재 합계 더 크면, 교체하세요 최대합 그것에.
단계 5) 인셀덤 공식 판매점인 j 배열의 끝에 도달하면 1씩 증가합니다. i 및 재설정 현재 합계 0합니다.
단계 6) 반복하세요 i 배열의 끝에 도달합니다. 최대합 그다음에는 가장 큰 부분 배열 합을 저장합니다.
별명 Code 간단한 접근 방식을 위해
function maximumSubarraySum(): input: array for all possible subArray from array: calculate sum of each subarray store the maximum subArray return the maximum sum
C++ 간단한 접근 방식 구현
#include <stdio.h> #include <iostream> using namespace std; void maximumSubarraySum(int array[], int n) { int max_sum = -1e9; int begin = 0; int end = 0; for (int i = 0; i < n; i++) { int current_sum = 0; for (int j = i; j < n; j++) { current_sum += array[j]; if (max_sum < current_sum) { max_sum = current_sum; begin = i; end = j; } } } cout << "largest sum is " << max_sum << endl; cout << "largest sum contiguous subarray: "; for (int i = begin; i <= end; i++) { cout << array[i] << "\t"; } } int main() { int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5}; maximumSubarraySum(array, sizeof(array) / sizeof(array[0])); }
출력:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Python 간단한 접근 방식 구현
def maximumSubarraySum(numbers): max_sum, begin, end = -1e9, 0, 0 for i in range(len(numbers)): current_sum = 0 for j in range(i, len(numbers)): current_sum += numbers[j] if max_sum < current_sum: max_sum = current_sum begin, end = i, j print("largest sum is ", max_sum) print("largest sum contiguous subarray: ", end='') for i in range(begin, end + 1): print(numbers[i], end='\t') numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5] maximumSubarraySum(numbers)
출력:
largest sum is 12 largest sum contiguous subarray: 5 1 6
카데인의 알고리즘을 이용한 연속 부분 배열의 최대 합 찾기
카데인 알고리즘은 두 개의 반복문 대신 하나의 반복문을 사용하는 동적 프로그래밍 방법입니다. 이 알고리즘은 배열에 양수와 음수가 혼합되어 있더라도, 적어도 하나의 값이 음수가 아니면 문제없이 처리할 수 있습니다.
연속된 부분 배열 중 가장 큰 합을 찾으려면 두 개의 변수만 필요합니다. 다음은 순서도입니다.
Kadane 알고리즘의 단계는 다음과 같습니다.
단계 1) 변수 두 개를 생성하세요. 현재 합계 최대합.
현재 합계 특정 배열 인덱스에서 끝나는 최대 합계를 유지하는 반면 최대합 지금까지 관찰된 가장 큰 합계 값을 저장합니다.
단계 2) 배열의 각 요소를 더합니다. 현재 합계그런 다음 아래 두 가지 조건을 확인하십시오.
- If 현재 합계 현재 요소보다 작으면 현재 합계 현재 요소가 됩니다.
- If 최대합 ~보다 작다. 현재 합계다음, 최대합 된다 현재 합계.
단계 3) 배열 전체에 대해 이전 단계를 반복한 후, 최대합 가장 큰 합을 갖는 연속 부분 배열입니다.
Kadane 알고리즘의 예
작은 배열을 사용하여 카데인 알고리즘을 시연하고, 가장 큰 합을 갖는 연속된 부분 배열을 찾는 모든 단계를 자세히 살펴봅니다.
주어진 배열이 다음과 같다고 가정해 봅시다.
다음은 카데인 알고리즘의 단계입니다.
단계 1) 변수 두 개를 생성하세요. 현재 합계 최대합INT_MIN에 할당합니다. 최대합 그리고 0에서 현재 합계여기서 INT_MIN은 최소 정수 값을 나타냅니다.
단계 2) 인덱스 0에서의 값은 4입니다. 따라서, 현재 합계 = 0 + 4 = 4. 이므로 현재 합계 보다 큼 최대합, 최대합 4이됩니다.
단계 3) 인덱스 1에서의 값은 -2입니다. 따라서, 현재 합계 = 4 + (-2) = 2.
이 시간 현재 합계 ~보다 작다. 최대합결과적으로, 그 값은 최대합 업데이트되지 않습니다.
단계 4) 다음 값은 1입니다. 이를 더하면 현재 합계 3을 줍니다. 왜냐하면 최대합 (4)는 여전히 보다 크다 현재 합계, 최대합 업데이트되지 않습니다.
단계 5) 인덱스 3에서의 값은 3입니다. 증가 현재 합계 3을 더하면 현재 합계 = 6.
이 경우, 최대합 보다 작다 현재 합계그래서 최대합 값으로 업데이트됩니다. 현재 합계.
단계 6) 배열의 마지막 요소는 -1입니다. 이를 더하면 현재 합계 5를 주는데, 이는 보다 작습니다. 최대합. 그래서, 최대합 6으로 유지됩니다.
배열의 끝에 도달했으므로 알고리즘은 여기서 종료됩니다. 이제 최대합 최댓값인 6을 포함합니다. 부분 배열은 {4, -2, 1, 3}입니다.
별명 Code 카데인의 알고리즘의 경우
function KadaneAlgorithm(): input: array maximum_sum, current_sum = 0 for each element in array: add the element with current_sum if current_sum is greater than the maximum_sum then maximum_sum = current_sum if current_sum is less than the element then current_sum = element return the value of maximum_sum
C++ Kadane 알고리즘 구현
#include <iostream> using namespace std; void kadane(int array[], int n) { int current_sum = 0; int max_sum = -1e9; // -1e9 means -1,000,000,000 for (int i = 0; i < n; i++) { current_sum += array[i]; if (max_sum < current_sum) { max_sum = current_sum; } if (current_sum < array[i]) { current_sum = array[i]; } } cout << "largest sum is " << max_sum << endl; } int main() { int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5}; kadane(array, sizeof(array) / sizeof(array[0])); }
출력:
largest sum is 12
Python Kadane 알고리즘 구현
def kadane(numbers): current_sum = 0 max_sum = -1e9 for i in range(len(numbers)): current_sum += numbers[i] if max_sum < current_sum: max_sum = current_sum if current_sum < numbers[i]: current_sum = numbers[i] print("largest sum is ", max_sum) kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])
출력:
largest sum is 12
가장 큰 합 연속 부분 배열에 대한 복잡성 분석
간단한 접근 방식은 두 개의 반복문을 사용하여 가능한 모든 부분 배열의 합을 계산하고 가장 큰 합을 찾는 것입니다. 이는 무차별 대입 방식이며, 각 반복문은 배열의 끝까지 실행됩니다. 정렬,주는 O(N²) 시간.
Kadane의 알고리즘은 단 하나의 루프만 사용하므로 시간 복잡도는 O(N)이고 추가 공간은 O(1)입니다. 100개의 요소로 이루어진 배열의 경우 간단한 접근 방식은 100 × 100 = 10,000번의 연산을 수행하는 반면 Kadane의 알고리즘은 100번의 연산만 수행하므로 입력이 큰 경우 속도가 크게 향상됩니다.
