Tìm tổng lớn nhất lấy mọi phần tử thứ K trong mảng 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ố nguyên k. Nhiệm vụ của chúng ta là Tìm tổng lớn nhất lấy mọi phần tử thứ K trong mảng.

Mô tả vấn đề:Chúng ta cần tìm tổng lớn nhất của các phần tử của mảng sao cho chúng cách nhau k chỉ mục. I.e. chúng ta cần tối đa hóa tổng,

sum =arr [i] + arr [i + k] + arr [i + 2 * k] +…. arr [i + p * k], sao cho (i + p * k)

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

Đầu vào

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

Đầu ra

9

Giải thích

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

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

Một giải pháp đơn giản cho vấn đề là sử dụng hai vòng lặp lồng nhau, vòng bên ngoài cho mỗi phần tử của mảng và vòng bên trong được sử dụng để tìm tổng của việc lấy mọi phần tử thứ k từ i. tức là sum =arr [i] + arr [i + k] + arr [i + 2 * k] +… + arr [i + p * k] sao cho (i + p * k)

Và trả về tổng số tiền tối đa.

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

Đầu ra

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

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

Ví dụ

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

Đầu ra

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