在 C++ 中查找数组中每个第 K 个元素的最大和
在这个问题中，我们得到一个数组 arr[] 和一个整数 k。我们的任务是找到数组中每个第 K 个元素的最大和。
问题描述：我们需要找到数组中元素相距k个索引的最大和。即我们需要最大化总和，
sum = arr[i] + arr[i+k] + arr[i + 2*k] + .... arr[i + p*k]，使得 (i + p*k) < n
让我们举个例子来理解这个问题，
输入
arr[] = {5, 3, −1, 2, 4, −5, 6}, k = 4输出结果9
解释
All sums of every kth element is5 + 4 = 9
3 − 5 = −2
−1 + 6 = 5
2
4
−5
6
The maximum is 9
解决方法
该问题的一个简单解决方案是使用两个嵌套循环，外部循环用于数组的每个元素，内部循环用于查找从 iie sum = arr[i] + arr[i + k] + arr[i + 2*k] + … + arr[i + p*k] 使得 (i + p*k) < n。
并返回最大和。
程序来说明我们的解决方案的工作，
示例
#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
以上是 在 C++ 中查找数组中每个第 K 个元素的最大和 的全部内容， 来源链接： utcz.com/z/322817.html
