Dãy con có tổng tối đa với ít nhất k phần tử ở xa trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm dãy con có tổng tối đa với ít nhất k phần tử ở xa.

Đối với điều này, chúng ta sẽ được cung cấp một mảng chứa các số nguyên và giá trị K. Nhiệm vụ của chúng ta là tìm dãy con có tổng lớn nhất sao cho tất cả các phần tử cách nhau ít nhất K phần tử.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//finding maximum sum subsequence
int maxSum(int arr[], int N, int k) {
   int MS[N];
   MS[N - 1] = arr[N - 1];
   for (int i = N - 2; i >= 0; i--) {
      if (i + k + 1 >= N)
         MS[i] = max(arr[i], MS[i + 1]);
      else
         MS[i] = max(arr[i] + MS[i + k + 1], MS[i + 1]);
   }
   return MS[0];
}
int main() {
   int N = 10, k = 2;
   int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
   cout << maxSum(arr, N, k);
   return 0;
}

Đầu ra

230