資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 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 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) < 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
更新於: 2021年3月12日
193 次檢視
廣告