C++에서 배열의 모든 K번째 요소를 취하는 최대 합 찾기

이 문제에서 배열 arr[]와 정수 k가 주어집니다. 우리의 임무는 배열의 모든 K번째 요소를 취하는 최대 합을 찾는 것입니다.

문제 설명:배열 요소가 k 인덱스 떨어져 있도록 배열 요소의 최대 합을 찾아야 합니다. 합계를 최대화해야 합니다.

합계 =arr[i] + arr[i+k] + arr[i + 2*k] + … arr[i + p*k], (i + p*k)

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

입력

arr[] = {5, 3, −1, 2, 4, −5, 6}, k = 4

출력

9

설명

All sums of every kth element is
5 + 4 = 9
3 − 5 = −2
−1 + 6 = 5
2
4
−5
6
The maximum is 9

솔루션 접근 방식

이 문제에 대한 간단한 해결책은 두 개의 중첩 루프를 사용하는 것입니다. 외부 루프는 배열의 각 요소에 대해 사용하고 내부 루프는 i에서 모든 k번째 요소를 취하는 합을 찾는 데 사용됩니다. 즉 sum =arr[i] + arr[i + k] + arr[i + 2*k] + … + arr[i + p*k] (i + p*k)

그리고 최대 합계를 반환합니다.

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

예시

#include <iostream>
using namespace std;
int findMaxSumK(int arr[], int n, int K){
   int maxSum = -1000;
   for (int i = 0; i < n; i++) {
      int current_Sum = 0;
      for (int j = i; j < n; j += K)
         current_Sum = current_Sum + arr[j];
         maxSum = max(maxSum, current_Sum);
   }
   return maxSum;
}
int main(){
   int arr[] = {5, 3, -1, 2, 4, -5, 6};
   int n = sizeof(arr) / sizeof(arr[0]);
   int K = 3;
   cout<<"The maximum sum taking every Kth element in the array is
   "<<findMaxSumK(arr, n, K);
   return (0);
}

출력

The maximum sum taking every Kth element in the array is 13

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

예시

#include <iostream>
using namespace std;
int findMaxSumK(int arr[], int n, int K) {
   int maxSum = -1000;
   int suffSum[n] = {0};
   for (int i = n - 1; i >= 0; i--) {
      if (i + K < n)
         suffSum[i] = suffSum[i + K] + arr[i];
      else
         suffSum[i] = arr[i];
         maxSum = max(maxSum, suffSum[i]);
   }
   return maxSum;
}
int main(){
   int arr[] = {5, 3, -1, 2, 4, -5, 6};
   int n = sizeof(arr) / sizeof(arr[0]);
   int K = 3;
   cout<<"The maximum sum taking every Kth element in the array is
   "<<findMaxSumK(arr, n, K);
   return (0);
}

출력

The maximum sum taking every Kth element in the array is 13