Tìm tổng lớn nhất lấy mỗi phần tử thứ K trong mảng C++

Mô tả vấn đề

Cho mảng arr[] và số nguyên k. Tìm tổng lớn nhất của các phần tử cách nhau đúng k chỉ số: arr[i] + arr[i+k] + arr[i+2k] + ... với i + p*k < n.

Ví dụ minh họa

Đầu vào:

arr[] = {5, 3, -1, 2, 4, -5, 6}, k = 4

Đầu ra:

9

Giải thích:

Các tổng cách k=4:
i=0: 5 + 4 = 9
i=1: 3 + (-5) = -2
i=2: -1 + 6 = 5
i=3: 2
i=4: 4
i=5: -5
i=6: 6
Max = 9

Phương pháp giải quyết

Cách 1 (O(n*k) - Lồng vòng lặp): Với mỗi i, tính tổng các phần tử i, i+k, i+2k....

Cách 2 (O(n) - Suffix Sum / DP): Tính từ cuối mảng về đầu: suffSum[i] = arr[i] + (i+k < n ? suffSum[i+k] : 0). Theo dõi max trong quá trình tính.

Chương trình minh họa (Cách 1)

#include <iostream>
using namespace std;

int findMaxSumK(int arr[], int n, int K) {
    int maxSum = -1000;
    for (int i = 0; i < n; i++) {
        int current_Sum = 0;
        for (int j = i; j < n; j += K)
            current_Sum += arr[j];
        maxSum = max(maxSum, current_Sum);
    }
    return maxSum;
}

Chương trình minh họa (Cách 2 - Hiệu quả)

#include <iostream>
using namespace std;

int findMaxSumK(int arr[], int n, int K) {
    int maxSum = -1000;
    int suffSum[n] = {0};
    for (int i = n - 1; i >= 0; i--) {
        if (i + K < n)
            suffSum[i] = suffSum[i + K] + arr[i];
        else
            suffSum[i] = arr[i];
        maxSum = max(maxSum, suffSum[i]);
    }
    return maxSum;
}

int main() {
    int arr[] = {5, 3, -1, 2, 4, -5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
    cout << "Tổng lớn nhất lấy mỗi phần tử thứ K là " << findMaxSumK(arr, n, K);
    return 0;
}

Kết quả đầu ra

Tổng lớn nhất lấy mỗi phần tử thứ K là 13