이 문제에서 배열 arr[]와 두 개의 정수 M과 K가 주어집니다. 우리의 임무는 주어진 배열의 요소를 사용하여 배열을 만드는 것입니다. 새 배열의 크기는 M이어야 하며 크기가 K보다 큰 하위 배열은 모든 요소를 동일하게 가질 수 없습니다. 생성된 배열에서 가능한 최대 합계를 출력해야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 - arr[] ={1, 2, 4, 5, 7 }, M =5, K =2
설명 - {7, 7, 5, 7, 7} 조건을 만족하는 배열 생성. 여기서 크기가 2보다 큰 하위 배열은 모든 요소를 동일하게 가질 수 없습니다.
이 문제를 해결하려면 최대값을 갖는 요소를 사용하여 배열을 생성해야 합니다. 그러나 최대 요소를 k 번 이상 사용할 수 없으므로 k 번 후에는 배열의 두 번째 최대 요소를 사용해야 합니다. 배열의 모든 k 최대값 뒤에 1초 최대값을 삽입하고 M 길이의 배열을 만듭니다. 최종 출력은 이 배열의 모든 요소의 합입니다.
예시
솔루션 구현을 보여주는 프로그램,
#include <iostream>
using namespace std;
long int arraySum(int arr[], int n, int m, int k){
int max1 = arr[0], max2 = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max1) {
max2 = max1;
max1 = arr[i];
}
else if (arr[i] > max2)
max2 = arr[i];
}
int max2count = m / (k + 1);
long int sum = max2count * max2 + (m - max2count) * max1;
return sum;
}
int main() {
int arr[] = { 1, 3, 6, 7, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int m = 9, k = 2;
cout<<"The maximum sum of array created from the given array such that no subarray of size greater than "<<k<<" will have same elements is ";
cout<<arraySum(arr, n, m, k);
return 0;
} 출력
The maximum sum of array created from the given array such that no subarray of size greater than 2 will have same elements is 60