C++에서 주어진 합계보다 작거나 같은 합계를 갖는 최대 합계 하위 배열

이 문제에서는 배열과 합계가 제공됩니다. 우리의 임무는 C++에서 주어진 합보다 작거나 같은 합을 갖는 최대 합 하위 배열을 찾는 프로그램을 만드는 것입니다.

합이 주어진 합보다 작거나 같은 n보다 작거나 같은 길이의 부분배열을 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력 - 배열 ={3, 5, 1, 8, 2, 9}, 합계 =25

출력 − 25

설명 − 합계가 25보다 작거나 같은 하위 배열은 {5, 1, 8, 2, 9}

최대 합계 하위 배열을 찾는 한 가지 간단한 방법은 배열을 반복하고 모든 하위 배열의 합계를 찾은 다음 가장 가깝거나 같은 합계를 찾는 것입니다. 그러나 이 방법은 두 개의 루프가 필요하므로 O(n*n)의 시간 복잡도를 갖습니다.

이 문제를 해결하는 더 효율적인 방법은 슬라이딩 창을 사용하는 것입니다. 방법. 여기에서 최대 합계로 현재 합계를 확인하고 비교를 기반으로 창에 요소를 더하거나 뺍니다.

예시

솔루션의 작동을 설명하는 프로그램,

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

출력

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