C++에서 크기가 k인 부분배열의 최대(또는 최소) 합 찾기

이 문제에서 배열 arr[]와 숫자 k가 주어집니다. 우리의 임무는 크기가 k인 부분배열의 최대(또는 최소) 합을 찾는 것입니다.

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

입력: arr[] ={55, 43, 12, 76, 89, 25, 99}, k =2

출력: 165

설명:

크기 2의 하위 배열은 합계 =76 + 89 =165

해결 방법

문제를 해결하는 간단한 방법은 k 크기의 모든 하위 배열을 찾은 다음 최대값으로 합계를 반환하는 것입니다.

또 다른 접근 방식 슬라이딩 창 을 사용 중입니다. 우리는 k 크기의 하위 배열의 합을 찾을 것입니다. 이를 위해 다음 k 크기의 하위 배열에서 마지막 인덱스 요소를 빼고 다음 인덱스 요소를 추가합니다.

그런 다음 최대값으로 하위 배열 합계를 반환합니다.

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

예

#include <iostream>
using namespace std;

int findMaxSumSubarray(int arr[], int n, int k) {
   
   if (n < k) {
      cout << "Invalid";
      return -1;
   }

   int maxSum = 0;
   for (int i=0; i<k; i++)
      maxSum += arr[i];
   int curr_sum = maxSum;
   for (int i=k; i<n; i++) {
      curr_sum += arr[i] - arr[i-k];
      maxSum = max(maxSum, curr_sum);
   }
   return maxSum;
}

int main() {
   
   int arr[] = {55, 43, 12, 76, 89, 25, 99};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 2;
   cout<<"The sum of subarray with max sum of size "<<k<<" is "<<findMaxSumSubarray(arr, n, k);
   return 0;
}

출력

The sum of subarray with max sum of size 2 is 165