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

ソリューションアプローチ

この問題の簡単な解決策は、2つのネストされたループを使用することです。外側のループは配列の各要素に使用され、内側のループは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