프로그램을 완료하는 단계를 살펴보겠습니다.
- 배열을 초기화합니다.
- 크기가 n인 max_sum 배열을 초기화합니다.
- 모든 인덱스의 최대 합계를 찾아 max_sum 배열에 저장합니다.
- 모든 요소의 합계를 계산하고 변수 합계에 저장합니다.
- i =k에서 n까지 반복하는 루프를 작성합니다.
- 합계에 a[i] - [i - k]를 더하세요.
- 결과를 최대 결과 합계로 업데이트합니다.
- 결과의 최대값인 sum + max_sum[i - k]로 결과를 업데이트합니다.
예시
코드를 봅시다.
#include<bits/stdc++.h>
using namespace std;
int getMaxSum(int a[], int n, int k) {
int maxSum[n];
maxSum[0] = a[0];
int currentMax = a[0];
for (int i = 1; i < n; i++) {
currentMax = max(a[i], currentMax+a[i]);
maxSum[i] = currentMax;
}
int sum = 0;
for (int i = 0; i < k; i++) {
sum += a[i];
}
int result = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i-k];
result = max(result, sum);
result = max(result, sum + maxSum[i-k]);
}
return result;
}
int main() {
int a[] = {5, 3, 7, -5, 6, 2, 1};
int k = 6;
cout << getMaxSum(a, 7, k) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
19
결론
튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.