Mảng con tổng tối đa có tổng nhỏ hơn hoặc bằng tổng đã cho trong C ++

Trong bài toán này, chúng ta cho một mảng và một tổng. Nhiệm vụ của chúng ta là tạo một chương trình sẽ tìm mảng con tổng lớn nhất có tổng nhỏ hơn hoặc bằng tổng đã cho trong c ++.

Chúng ta phải tìm mảng con có độ dài bất kỳ nhỏ hơn hoặc bằng n có tổng nhỏ hơn hoặc bằng tổng đã cho.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - mảng ={3, 5, 1, 8, 2, 9}, sum =25

Đầu ra - 25

Giải thích - Các mảng con có tổng nhỏ hơn hoặc bằng 25 là {5, 1, 8, 2, 9}

Một phương pháp đơn giản để tìm mảng con có tổng lớn nhất là bằng cách lặp qua mảng và tìm tổng của tất cả mảng con rồi tìm tổng gần nhất hoặc bằng. Nhưng phương pháp này sẽ có độ phức tạp về thời gian là O (n * n) vì yêu cầu hai vòng lặp.

Một phương pháp hiệu quả hơn để giải quyết vấn đề này là sử dụng cửa sổ trượt phương pháp. Trong đó, chúng tôi sẽ kiểm tra tổng hiện tại với tổng tối đa và thêm hoặc trừ các 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 của chúng tôi,

#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<<"The maximum sum of subarray with sum less than or equal to "<<sum<<" is "<<maxSumsubarray(arr, n, sum);
   return 0;
}

Đầu ra

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