최대 하위 어레이 문제는 최대 슬라이스 문제와 동일합니다. 이 자습서에서는 C++ 코딩의 문제에 대해 설명합니다. 질문은 다음과 같습니다. 배열 내에서 가능한 연속 숫자 시퀀스의 최대 합은 얼마입니까? 이것은 전체 배열을 의미할 수 있습니다. 이 문제와 모든 언어로 된 솔루션을 최대 하위 배열 문제라고 합니다. 배열은 가능한 음수를 가질 수 있습니다.
솔루션은 효율적이어야 합니다. 가장 빠른 시간 복잡도를 가져야 합니다. 현재로서는 솔루션에 대한 가장 빠른 알고리즘이 과학 커뮤니티에서 Kadane의 알고리즘으로 알려져 있습니다. 이 기사에서는 C++를 사용한 Kadane의 알고리즘에 대해 설명합니다.
데이터 예
다음 벡터(배열)를 고려하십시오.
벡터 < 정수 > A = { 5 , - 7 , 삼 , 5 , - 둘 , 4 , - 1 } ;
최대 합계가 있는 슬라이스(하위 배열)는 {3, 5, -2, 4} 시퀀스이며 합계는 10입니다. 전체 배열을 포함하여 다른 가능한 시퀀스는 최대 합계를 제공하지 않습니다. 값은 10입니다. 전체 배열은 최대 합계가 아닌 7의 합계를 제공합니다.
다음 벡터를 고려하십시오.
벡터 < 정수 > B = { - 둘 , 1 , - 삼 , 4 , - 1 , 둘 , 1 , - 5 , 4 } ;
최대 합계가 있는 슬라이스(하위 배열)는 합계 6을 제공하는 시퀀스 {4, −1, 2, 1}입니다. 최대 합계에 대한 하위 배열 내에는 음수가 있을 수 있습니다.
다음 벡터를 고려하십시오.
벡터 < 정수 > C = { 삼 , 둘 , - 6 , 4 , 0 } ;
최대 합을 갖는 슬라이스(하위 배열)는 합이 5인 시퀀스 {3, 2}입니다.
다음 벡터를 고려하십시오.
벡터 < 정수 > D = { 삼 , 둘 , 6 , - 1 , 4 , 5 , - 1 , 둘 } ;
최대 합계가 있는 하위 배열은 {3, 2, 6, -1, 4, 5, -1, 2} 시퀀스이며 합계는 20입니다. 전체 배열입니다.
다음 벡터를 고려하십시오.
벡터 < 정수 > 전자 = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , 열 다섯 , 4 , - 8 , - 열 다섯 , - 22 } ;
여기에 최대 합계를 가진 두 개의 하위 배열이 있습니다. 더 높은 합이 최대 부배열 문제에 대한 해(답)로 간주되는 것이다. 하위 배열은 합이 12인 {5, 7}과 합이 35인 {6, 5, 10, -5, 15, 4}입니다. 물론 합이 35인 슬라이스는 다음과 같습니다. 대답.
다음 벡터를 고려하십시오.
벡터 < 정수 > 에프 = { - 4 , 10 , 열 다섯 , 9 , - 5 , - 이십 , - 삼 , - 12 , - 삼 , 4 , 6 , 삼 , 둘 , 8 , 삼 , - 5 , - 둘 } ;
최대 합계를 가진 두 개의 하위 배열이 있습니다. 더 높은 합이 최대 하위 배열 문제에 대한 솔루션으로 간주되는 것입니다. 하위 배열은 합이 34인 {10, 15, 9}와 합이 26인 {4, 6, 3, 2, 8, 3}입니다. 물론 합이 34인 슬라이스는 다음과 같습니다. 문제는 더 높은 합계를 가진 하위 배열이 아니라 가장 높은 합계를 가진 하위 배열을 찾는 것이기 때문입니다.
Kadane 알고리즘 개발
튜토리얼의 이 섹션에 있는 정보는 Kadane의 원본 작업이 아닙니다. Kadane의 알고리즘을 가르치는 저자 자신의 방법입니다. 누적 합계와 함께 위의 벡터 중 하나가 다음 표에 있습니다.
| 데이터 | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | 열 다섯 | 4 | -8 | -열 다섯 | -22 |
| 누계 | 5 | 12 | 8 | -둘 | -8 | -둘 | 삼 | 13 | 8 | 23 | 27 | 이십 일 | 16 | -6 |
| 인덱스 | 0 | 1 | 둘 | 삼 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 열하나 | 12 | 13 |
인덱스에 대한 누적 합계는 인덱스에 대한 값을 포함한 모든 이전 값의 합계입니다. 여기에 최대 합을 갖는 두 개의 시퀀스가 있습니다. 그것들은 합이 12인 {5, 7}과 합이 35인 {6, 5, 10, -5, 15, 4}입니다. 합이 35인 시퀀스가 원하는 것입니다. .
누계의 경우 값 12와 27인 두 개의 피크가 있습니다. 이 피크는 두 시퀀스의 마지막 인덱스에 해당합니다.
따라서 Kadane 알고리즘의 아이디어는 주어진 배열에서 왼쪽에서 오른쪽으로 이동하면서 발생하는 최대 합을 비교하면서 누계를 계산하는 것입니다.
누적 합계와 함께 위의 또 다른 벡터가 다음 표에 있습니다.
최대 합계가 있는 두 개의 시퀀스가 있습니다. 그들은 {10, 15, 9}이며 합계는 34입니다. 및 {4, 6, 3, 2, 8, 3}의 합은 26입니다. 합 34를 제공하는 시퀀스가 원하는 것입니다.
누계의 경우 값 30과 13인 두 개의 피크가 있습니다. 이 피크는 두 시퀀스의 마지막 인덱스에 해당합니다.
다시, Kadane 알고리즘의 아이디어는 주어진 배열에서 왼쪽에서 오른쪽으로 이동하면서 발생하는 최대 합을 비교하면서 누계를 계산하는 것입니다.
C++의 Kadane 알고리즘에 의한 코드
기사의 이 섹션에 제공된 코드는 반드시 Kadane이 사용한 코드는 아닙니다. 그러나 그것은 그의 알고리즘에 의한 것입니다. 다른 많은 C++ 프로그램과 마찬가지로 이 프로그램은 다음으로 시작합니다.
#include#포함<벡터>
네임스페이스 std 사용
입력 및 출력을 담당하는 iostream 라이브러리가 포함되어 있습니다. 표준 네임스페이스가 사용됩니다.
Kadane 알고리즘의 아이디어는 주어진 배열에서 왼쪽에서 오른쪽으로 이동하면서 발생하는 최대 합계를 비교하면서 누계를 갖는 것입니다. 알고리즘의 기능은 다음과 같습니다.
int maxSunArray ( 벡터 < 정수 > & ㅏ ) {int N = A.크기 ( ) ;
정수 최대 합계 = A [ 0 ] ;
int runTotal = A [ 0 ] ;
~을 위한 ( 정수 나 = 1 ; 나 < N; 나는 ++ ) {
정수 tempRunTotal = runTotal + A [ 나 ] ; // A보다 작을 수 있음 [ 나 ]
만약에 ( ㅏ [ 나 ] > 임시 실행 합계 )
총 실행 = A [ 나 ] ; // 안에 사례 ㅏ [ 나 ] 누계보다 큽니다.
또 다른
실행 합계 = 임시 실행 합계;
만약에 ( 총 실행 > 최대 금액 ) // 모든 최대 합계 비교
최대 합계 = 실행 합계;
}
반품 최대 금액;
}
주어진 배열(벡터)의 크기, N이 결정됩니다. 변수 maxSum은 가능한 최대 합계 중 하나입니다. 배열에는 최소 하나의 최대 합계가 있습니다. 변수 runTotal은 각 인덱스의 누적 합계를 나타냅니다. 둘 다 배열의 첫 번째 값으로 초기화됩니다. 이 알고리즘에서 배열의 다음 값이 누계보다 크면 다음 값이 새 누계가 됩니다.
하나의 주요 for 루프가 있습니다. 스캔은 변수 maxSum 및 runTotal을 지정된 배열의 첫 번째 요소인 A[0]으로 초기화하기 때문에 0이 아닌 1에서 시작합니다.
for-loop에서 첫 번째 문은 모든 이전 값의 누적 합계에 현재 값을 더하여 임시 누계를 결정합니다.
다음으로 if/else 구문이 있습니다. 현재 값만 지금까지의 누적 합계보다 크면 해당 단일 값이 누적 합계가 됩니다. 지정된 배열의 모든 값이 음수인 경우 특히 유용합니다. 이 경우 가장 높은 음수 값만 최대값(답)이 됩니다. 현재 값만 현재까지 임시 누계보다 크지 않은 경우 누계는 이전 누계에 현재 값을 더한 값이 됩니다. 이는 if/else 구문의 else 부분입니다.
for-loop의 마지막 코드 세그먼트는 이전 시퀀스(하위 배열)에 대한 이전 최대 합계와 현재 시퀀스에 대한 현재 최대 합계 중에서 선택합니다. 따라서 더 높은 값이 선택됩니다. 하나 이상의 최대 하위 배열 합계가 있을 수 있습니다. 어레이가 왼쪽에서 오른쪽으로 스캔되기 때문에 누적 합계가 오르락내리락한다는 점에 유의하십시오. 음수 값을 만나면 떨어집니다.
최종적으로 선택된 최대 하위 배열 합계는 for 루프 이후에 반환됩니다.
Kadane의 알고리즘 기능에 적합한 C++ 주 기능의 내용은 다음과 같습니다.
벡터 < 정수 > A = { 5 , - 7 , 삼 , 5 , - 둘 , 4 , - 1 } ; // { 삼 , 5 , - 둘 , 4 } - > 10int ret1 = maxSunArray ( ㅏ ) ;
쫓다 << ret1 << 끝;
벡터 < 정수 > B = { - 둘 , 1 , - 삼 , 4 , - 1 , 둘 , 1 , - 5 , 4 } ; // { 4 , - 1 , 둘 , 1 } - > 6
int ret2 = maxSunArray ( 비 ) ;
쫓다 << 렛2 << 끝;
벡터 < 정수 > C = { 삼 , 둘 , - 6 , 4 , 0 } ; // { 삼 , 둘 } - > 5
int ret3 = maxSunArray ( 씨 ) ;
쫓다 << ret3 << 끝;
벡터 < 정수 > D = { 삼 , 둘 , 6 , - 1 , 4 , 5 , - 1 , 둘 } ; // { 삼 , 둘 , 6 , - 1 , 4 , 5 , - 1 , 둘 } - > 5
int ret4 = maxSunArray ( 디 ) ;
쫓다 << 넷4 << 끝;
벡터 < 정수 > 전자 = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , 열 다섯 , 4 , - 8 , - 열 다섯 , - 22 } ; // { 6 , 5 , 10 , - 5 , 열 다섯 , 4 } - > 35
int ret5 = maxSunArray ( 그리고 ) ;
쫓다 << ret5 << 끝;
벡터 < 정수 > 에프 = { - 4 , 10 , 열 다섯 , 9 , - 5 , - 이십 , - 삼 , - 12 , - 삼 , 4 , 6 , 삼 , 둘 , 8 , 삼 , - 5 , - 둘 } ; // { 10 , 열 다섯 , 9 } - > 3. 4
int ret6 = maxSunArray ( 에프 ) ;
쫓다 << 오른쪽 6 << 끝;
이를 통해 출력은 다음과 같습니다.
10
6
5
이십
35
3. 4
여기에서 각 줄 대답은 순서대로 주어진 배열에 해당합니다.
결론
Kadane 알고리즘의 시간 복잡도는 O(n)이며, 여기서 n은 주어진 배열의 요소 수입니다. 이 시간 복잡도는 최대 하위 배열 문제에서 가장 빠릅니다. 더 느린 다른 알고리즘이 있습니다. Kadane 알고리즘의 아이디어는 주어진 배열에서 왼쪽에서 오른쪽으로 이동하면서 발생하는 최대 합계를 비교하면서 누계를 계산하는 것입니다. 현재 값만 지금까지의 누계보다 크면 해당 단일 값이 새 누계가 됩니다. 그렇지 않으면 새 누적 합계는 예상대로 주어진 배열을 스캔할 때 이전 누적 합계에 현재 요소를 더한 것입니다.
다른 가능한 하위 배열에 대해 둘 이상의 최대 합계가 있을 수 있습니다. 가능한 모든 하위 배열에 대해 가장 높은 최대 합계가 선택됩니다.
선택한 최대 합계의 범위에 대한 제한 지수는 무엇입니까? – 그것은 다른 시간 동안의 토론입니다!
크리스