Hãy xem các bước để hoàn thành chương trình.
- Khởi tạo mảng.
- Khởi tạo mảng max_sum có kích thước n.
- Tìm tổng tối đa cho mọi chỉ mục và lưu trữ nó trong mảng max_sum.
- Tính tổng của tất cả các phần tử và lưu trữ nó trong một tổng có thể thay đổi.
- Viết một vòng lặp lặp lại từ i =k đến n.
- Thêm [i] - a [i - k] vào tổng.
- Cập nhật kết quả với tối đa của kết quả, tổng.
- Cập nhật kết quả với max of result, sum + max_sum [i - k].
Ví dụ
Hãy xem mã.
#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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
19
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.