이 튜토리얼에서 우리는 최소 k 개의 먼 요소를 가진 최대 합 부분 수열을 찾는 프로그램에 대해 논의할 것입니다.
이를 위해 정수와 값 K를 포함하는 배열이 제공됩니다. 우리의 임무는 모든 요소가 최소한 K 요소 떨어져 있도록 최대 합을 갖는 하위 시퀀스를 찾는 것입니다.
예시
#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; }
출력
230