Maximum Sum Subarray Having Sum ≤ Given Sum ใน C++

ภาพรวมปัญหา

มีอาร์เรย์และค่า sum ที่กำหนด หา Subarray ที่มีผลรวม ≤ sum ที่กำหนด และผลรวมมากที่สุด

ตัวอย่าง: [3,5,1,8,2,9], sum=25 → Output: 25 (subarray {5,1,8,2,9})

อัลกอริทึม (Sliding Window)

1. sum = arr[0], overallMax = 0, start = 0
2. for i = 1 ถึง n-1:
   • ถ้า sum ≤ maxSum: overallMax = max(overallMax, sum)
   • while sum + arr[i] > maxSum และ start < i: sum -= arr[start], start++
   • sum += arr[i]
3. ตรวจสอบรอบสุดท้าย: ถ้า sum ≤ maxSum → overallMax = max(overallMax, sum)
4. return overallMax

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

int findMax(int a, int b){ return (a > b) ? a : b; }

int maxSumsubarray(int arr[], int n, int maxSum){
    int sum = arr[0], overallMax = 0, start = 0;
    for (int i = 1; i < n; i++) {
        if (sum <= maxSum) overallMax = findMax(overallMax, sum);
        while (sum + arr[i] > maxSum && start < i) {
            sum -= arr[start];
            start++;
        }
        sum += arr[i];
    }
    if (sum <= maxSum) overallMax = findMax(overallMax, sum);
    return overallMax;
}

int main(){
    int arr[] = {3, 1, 4, 7, 2, 9, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 20;
    cout << "The maximum sum of subarray with sum less than or equal to " << sum << " is " << maxSumsubarray(arr, n, sum);
    return 0;
}

ผลลัพธ์

The maximum sum of subarray with sum less than or equal to 20 is 18