이 문제에서는 크기가 n이고 정수 k인 배열 arr[]이 제공됩니다. 우리의 임무는 배열의

문제 설명 − 서로 k 거리에 있는 요소를 고려한 하위 시퀀스의 최대 합을 찾아야 합니다.

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

입력

arr[] = {6, 2, 5, 1, 9, 11, 4} k = 2

출력

16

설명

All possible sub−sequences of elements that differ by k or more.
{6, 1, 4}, sum = 11
{2, 9}, sum = 11
{5, 11}, sum = 16
{1, 4}, sum = 5
...
maxSum = 16

솔루션 접근 방식

이 문제에 대한 해결책은 동적 프로그래밍을 사용하는 것입니다. 솔루션의 경우 배열의 현재 요소까지 가능한 최대 합을 찾습니다. 그리고 그것을 DP[i]에 저장합니다. 이를 위해 가능한 최대 합을 찾을 것입니다. i 번째 인덱스의 경우 현재 인덱스 값을 추가하면 하위 시퀀스 합이 증가하는지 확인해야 합니다.

if( DP[i − (k+1)] + arr[i] > DP[i − 1] )
−> DP[i] = DP[i − (k+1)] + arr[i]
otherwise DP[i] = DP[i−1]

동적 배열의 최대 요소는 최대 하위 시퀀스 합계를 제공합니다.

알고리즘

초기화 -

maxSumSubSeq = −1, maxSumDP[n]

1단계 -

Initialize maxSumDP[0] = arr[0]

2단계 -

Loop for i −> 1 to n.

2.1단계 -

if i < k −> maxSumDP[i] = maximum of arr[i] or
maxSumDP[i− 1].

2.2단계 -

else, maxSumDP[i] = maximum of arr[i] or maxSumDP[i − (k + 1)] + arr[i].

3단계 -

Find the maximum value of all elements from maxSumDP and store
it to maxSumSubSeq.

4단계 -

Return maxSumSubSeq

예시

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

#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
   if(a > b)
   return a;
   return b;
}
int calcMaxSumSubSeq(int arr[], int k, int n) {
   int maxSumDP[n];
   int maxSum = −1;
   maxSumDP[0] = arr[0];
   for (int i = 1; i < n; i++){
      if(i < k ){
         maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − 1]);
      }
      else
      maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − (k +
      1)] + arr[i]);
   }
   for(int i = 0; i < n; i++)
   maxSum = retMaxVal(maxSumDP[i], maxSum);
   return maxSum;
}
int main() {
   int arr[] = {6, 2, 5, 1, 9, 11, 4};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   cout<<"The maximum sum possible for a sub−sequence such
   that no two elements appear at a distance < "<<k<<" in the array is "<<calcMaxSumSubSeq(arr, k, n);
   return 0;
}

출력

The maximum sum possible for a sub−sequence such that no two
elements appear at a distance < 2 in the array is 16