ซับอาร์เรย์ผลรวมมากที่สุดที่มีอย่างน้อย k ตัวเลขใน C++

โจทย์

มาดูขั้นตอนในการทำโปรแกรม

• กำหนดอาร์เรย์
• กำหนดอาร์เรย์ max_sum ขนาด n
• หาผลรวมมากที่สุดสำหรับทุกดัชนีและเก็บไว้ในอาร์เรย์ max_sum
• คำนวณผลรวมของทุกองค์ประกอบและเก็บไว้ในตัวแปร sum
• เขียนลูปที่วนรอบจาก i = k ถึง n
  • บวก a[i] - a[i - k] เข้าไปใน sum
  • อัปเดตผลลัพธ์ด้วยค่าสูงสุดของ result และ sum
  • อัปเดตผลลัพธ์ด้วยค่าสูงสุดของ result และ 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

สรุป

หากคุณมีคำถามในบทช่วยสอนนี้ ให้กล่าวถึงในส่วนความคิดเห็น