Kadence의 알고리즘: 최대 합 연속 하위 배열
사라 첸
가장 큰 합계 연속 하위 배열은 무엇입니까?
하위 배열은 배열의 연속적인 부분입니다. 배열의 단일 요소일 수도 있고 배열의 일부일 수도 있습니다. 합이 가장 큰 연속 부분배열은 합이 최대인 부분배열을 의미한다.
예를 들어 배열은 {-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} = 11의 합은 위 배열의 하위 배열의 가능한 모든 조합에서 최대 합입니다. 따라서 위 배열의 경우 최대 하위 배열은 {5,1,6}입니다.
Kadence의 알고리즘: 최대 합 연속 하위 배열
가장 큰 합계 연속 부분배열을 해결하는 간단한 접근 방식
이 문제를 해결하는 간단한 방법은 두 개의 루프를 사용하여 모든 하위 배열을 찾고 합계를 계산한 다음 최대값을 찾는 것입니다.
다음은 가장 큰 연속 하위 배열 합계를 찾는 간단한 접근 방식에 대한 순서도입니다. 가능한 모든 하위 배열을 살펴보게 되므로 이는 무차별 대입 접근 방식입니다.
이를 수행하는 간단한 단계는 다음과 같습니다.
단계 1) 최소 정수 값으로 max_sum을 초기화하고 변수 "begin" 및 "end"에 XNUMX을 할당합니다.
단계 2) i와 j를 배열의 인덱스로 설정합니다. 여기서 "j"는 "i"보다 큽니다. 하위 배열의 시작 인덱스를 나타내고, "j"는 하위 배열의 끝 인덱스를 나타냅니다.
단계 3) "Current_sum"은 하위 배열의 합계를 보유합니다. 현재 합계를 계산한 후 current_sum이 max_sum보다 큰지 확인합니다.
단계 4) current_sum이 더 크면 max_sum을 현재 합계로 바꿉니다.
단계 5) "j"가 배열의 끝에 도달했는지 확인하십시오. "j"가 배열의 끝에 도달하면 "i"를 증가시키고 current_sum 값을 0으로 변경합니다.
단계 6) "i"가 배열의 끝에 도달할 때까지 이 모든 단계를 수행하십시오.
단계 7) 이 두 루프가 끝나면 max_sum은 가장 큰 하위 배열 합계를 보유합니다.
간단한 접근 방식을 위한 의사 코드
function maximumSubarraySum():
input: array
for all possible subArray from array:
calculate sum of each sub array
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의 알고리즘
Kadane의 알고리즘은 일종의 "동적 프로그래밍" 방법입니다. 여기서는 두 개의 루프 대신 하나의 루프를 사용합니다. Kadane 알고리즘의 일반적인 구현은 양수 배열에만 작동합니다.
가장 큰 합계 연속 하위 배열을 찾으려면 두 개의 변수만 필요합니다. Kadane 알고리즘의 순서도는 다음과 같습니다.
Kadane 알고리즘의 단계는 다음과 같습니다.
단계 1) current_sum과 max_sum이라는 두 개의 변수를 만듭니다.
“Current_sum”은 특정 배열 인덱스로 끝나는 최대 합계 값을 유지하고, “max_sum”은 지금까지의 최대 합계 값을 저장합니다.
단계 2) 각 배열 요소에 대해 current_sum과 함께 값을 추가합니다. 그런 다음 아래 두 가지 조건을 확인하겠습니다.
- current_sum이 현재 요소보다 작으면 current_sum 값이 현재 요소가 됩니다.
- max_sum이 current_sum보다 작으면 max_sum은 current_sum이 됩니다.
단계 3) 전체 배열에 대해 이전 단계를 수행하면 "max_sum" 변수에서 가장 큰 합계의 연속 하위 배열을 갖게 됩니다.
Kadane 알고리즘의 예
우리는 작은 크기의 배열을 사용하여 Kadanes의 알고리즘을 시연하고 가장 큰 합계 연속 부분 배열을 찾는 모든 단계에 대해 논의할 것입니다.
주어진 배열이 다음과 같다고 가정해 보겠습니다.
Kadane 알고리즘의 단계는 다음과 같습니다.
단계 1) current_sum과 max_sum이라는 두 개의 변수를 만듭니다. max_sum에 INT_MIN을 할당하고 current_sum에 XNUMX을 할당합니다. (여기서 INT_MIN은 최소 정수를 의미합니다.)
단계 2) 인덱스 0에서 값은 4입니다. 따라서 current_sum = 0 + 4 또는 4입니다. 여기서 current_sum은 max_sum보다 크며 max_sum은 4가 됩니다.
단계 3) 인덱스 1에서 값은 -2입니다. 따라서 current_sum = 4 + (-2) 또는 2입니다.
이번에는 current_sum이 max_sum보다 작습니다. 결과적으로 max_sum 값은 업데이트되지 않습니다.
단계 4) 다음 값은 1입니다. 이것을 current_sum에 추가하면 current_sum은 3이 됩니다. 그래도 max_sum은 current_sum보다 큽니다. 따라서 max_sum은 업데이트되지 않습니다.
단계 5) 인덱스 3에서 값은 3입니다. current_sum을 6씩 증가시켜 값을 업데이트하겠습니다. 따라서 current_sum은 XNUMX이 됩니다.
이 경우 max_sum은 current_sum보다 작습니다. 따라서 max_sum은 current_sum 값으로 업데이트됩니다.
단계 6) 배열의 마지막 요소에는 -1이 있습니다. 이것을 current_sum과 함께 추가하면 current_sum은 5가 되며 이는 max_sum보다 작습니다. 따라서 max_sum은 6으로 유지됩니다.
배열의 끝에 도달하면 알고리즘이 여기서 끝납니다. 이제 "max_sum"에는 최대 합계 하위 배열이 포함됩니다. 5입니다. 하위 배열은 {4,-2,1,3}입니다.
Kadane 알고리즘의 의사 코드
function KadaneAlgorithm():
input: array
maximum_sum, current_sum = 0
for each elements 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 -10000000
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
가장 큰 합 연속 부분 배열에 대한 복잡성 분석
간단한 접근 방식은 두 개의 루프를 사용합니다. 이 방법은 가능한 모든 하위 배열 합계를 계산하여 가장 큰 것을 찾습니다. 그것은 무차별적인 접근 방식입니다. 각 루프는 해당 루프가 끝날 때까지 실행됩니다. 정렬.
배열의 총 개수가 다음과 같은 경우 N 그런 다음 두 개의 루프를 사용하여 N을 거치게 됩니다.2 요소. 결과적으로 가장 큰 합 연속 부분 배열을 찾는 간단한 접근 방식의 시간 복잡도는 다음과 같습니다. O(N2). 여기서 “O”는 복잡도 함수를 의미합니다.
반면, Kadane의 알고리즘은 최대 연속 합계 하위 배열을 찾는 동적 프로그래밍 방법입니다. 예제나 코드를 따라가면 루프를 하나만 사용하고 있음을 알 수 있습니다.
결과적으로 입력 배열의 크기가 N, 그러면 카다네 알고리즘의 시간 복잡도는 O(N)이 됩니다. 이는 간단한 접근 방식보다 빠릅니다. 예를 들어, 100개의 요소를 포함하는 배열입니다. 간단한 접근 방식은 100*100 또는 10,000 CPU 시간이 걸립니다. 하지만 카다네 알고리즘은 100 CPU 시간만 걸립니다.
