C++ 프로그램에서 최소 k 개의 먼 요소가 있는 최대 합 하위 시퀀스

이 문제에서는 크기가 n이고 숫자가 k인 배열 arr[]이 제공됩니다. 우리의 임무는 최소 k개의 먼 요소를 가진 최대 합 부분 수열을 찾는 프로그램을 만드는 것입니다.

문제 설명 − 인덱스가 k 거리에 있고 합이 최대인 배열에서 부분배열의 요소를 가져오도록 부분배열의 합을 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

arr[] = {2, 3, 7, 9, 2, 8, 3}

출력

15

설명

All subsequences that satisfy the given condition,
{2, 9, 3}, Sum = 14
{3, 2}, Sum = 5
{7, 8}, Sum = 15

해결 방법

문제에 대한 간단한 해결책은 주어진 조건을 만족하는 모든 가능한 부분배열을 찾는 것입니다. 모든 배열의 합을 구하고 모든 배열의 최대값을 반환합니다.

문제에 대한 보다 효율적인 솔루션은 현재 요소까지 최대 합계를 저장하는 배열을 생성하여 동적 프로그래밍 접근 방식을 사용하는 것입니다. 현재 요소의 경우 합계로 고려하거나 합계를 위해 버릴 수 있으며, 현재 인덱스까지 합계가 증가하는 것을 선택합니다.

합에 대해 고려하면 sum[i] =sum[i + k + 1] + arr[i+1]그렇지 않으면 합계에 대해 버리고 sum[i] =sum[i+1]그리고 마지막에 sum[0]에 있는 최대 합계를 반환합니다.

예

우리 솔루션의 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
int calcMaxSubSeqSum(int arr[], int N, int k){
   int maxSumDP[N];
   maxSumDP[N − 1] = arr[N − 1];
   for (int i = N − 2; i >= 0; i−−) {
      if (i + k + 1 >= N)
         maxSumDP[i] = max(arr[i], maxSumDP[i + 1]);
      else
         maxSumDP[i] = max(arr[i] + maxSumDP[i + k + 1], maxSumDP[i + 1]);
   }
   return maxSumDP[0];
}
int main() {
   int N = 10, k = 2;
   int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
   cout<<"The maximum sum subsequence with at−least k distant elements is "<<calcMaxSubSeqSum(arr, N, k);
   return 0;
}

출력

The maximum sum subsequence with at-least k distant elements is 230