Trong bài toán này, ta được cho một mảng và một tổng. Nhiệm vụ: viết chương trình tìm tổng dãy con lớn nhất có tổng nhỏ hơn hoặc bằng tổng cho trước trong C++.
Ta phải tìm dãy con bất kỳ độ dài ≤ n có tổng ≤ tổng cho trước.
Hãy xem ví dụ:
Input – array = {3, 5, 1, 8, 2, 9}, sum = 25
Output – 25
Giải thích – Các dãy con có tổng ≤ 25: {5, 1, 8, 2, 9}
Phương pháp đơn giản: duyệt mảng, tính tổng tất cả dãy con, tìm tổng gần nhất hoặc bằng. Độ phức tạp O(n^2) do hai vòng lặp.
Phương pháp hiệu quả hơn: dùng kỹ thuật cửa sổ trượt (sliding window). Kiểm tra tổng hiện tại với tổng lớn nhất, thêm/bớt phần tử vào cửa sổ dựa trên so sánh.
Ví dụ
Chương trình minh họa hoạt động của giải pháp:
#include <iostream> using namespace std; int findMax(int a, int b){ if(a>b) return a; return 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<<"Tổng lớn nhất của dãy con với tổng ≤ "<<sum<<" là "<<maxSumsubarray(arr, n, sum); return 0; }Kết quả
Tổng lớn nhất của dãy con với tổng nhỏ hơn hoặc bằng 20 là 18