Tìm tổng tối đa (hoặc tối thiểu) của một mảng con có kích thước k trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] và một số k. Nhiệm vụ của chúng ta là Tìm tổng lớn nhất (hoặc tối thiểu) của một mảng con có kích thước k.

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

Đầu vào: arr [] ={55, 43, 12, 76, 89, 25, 99}, k =2

Đầu ra: 165

Giải thích:

Mảng con có kích thước 2 có sum =76 + 89 =165

Phương pháp tiếp cận giải pháp

Một cách tiếp cận đơn giản để giải quyết vấn đề là tìm tất cả k mảng con có kích thước và sau đó trả về tổng có giá trị lớn nhất.

Cách tiếp cận khác đang sử dụng cửa sổ trượt, chúng ta sẽ tìm tổng của k mảng con có kích thước. Đối với điều này, mảng con có kích thước k tiếp theo, chúng tôi sẽ trừ phần tử chỉ mục cuối cùng và thêm phần tử chỉ mục tiếp theo.

Và sau đó trả về tổng của mảng con với giá trị lớn nhất.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

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

Đầu ra

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