หาผลรวมสูงสุดโดยการนำสมาชิกทุก K ตัวในอาร์เรย์ใน C++

คำอธิบายปัญหา

ได้รับอาร์เรย์ arr[] และจำนวนเต็ม k ต้องการหา ผลรวมสูงสุด (Maximum Sum) โดยการเลือกสมาชิกที่ห่างกัน k ตำแหน่ง

สูตร: sum = arr[i] + arr[i+k] + arr[i+2k] + ... + arr[i+pk] โดยที่ i + p*k < n

ตัวอย่าง

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

Output: 9

คำอธิบาย: ผลรวมทุกชุดที่ห่าง k=4:

• เริ่ม index 0: 5 + 4 = 9
• เริ่ม index 1: 3 + (-5) = -2
• เริ่ม index 2: -1 + 6 = 5
• เริ่ม index 3: 2
• เริ่ม index 4: 4
• เริ่ม index 5: -5
• เริ่ม index 6: 6

แนวทางแก้ปัญหา

วิธีที่ 1: Two Nested Loops (Simple)

ลูปนอก: ทุก index เริ่มต้น (0 ถึง n-1)
ลูปใน: สะสมผลรวมทุก k ตัว → Time: O(n²/k) ≈ O(n²)

วิธีที่ 2: Suffix Sum (DP) - O(n)

คำนวณย้อนกลับ: suffSum[i] = arr[i] + suffSum[i+k] (ถ้า i+k < n)
แล้วหา max(suffSum[i]) ทุก i

โค้ดตัวอย่าง C++ (ทั้งสองวิธี)

วิธีที่ 1: Nested Loops

#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;
}

วิธีที่ 2: Suffix Sum (เร็วกว่า)

#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 << "The maximum sum taking every Kth element in the array is " << findMaxSumK(arr, n, K);
    return 0;
}

ผลลัพธ์

The maximum sum taking every Kth element in the array is 13