Chọn tổng M phần tử tối đa sao cho các phần tử lặp lại liền kề không vượt quá K trong C ++

Trong bài toán này, chúng ta được cung cấp mảng arr [] và hai số nguyên M và K. Nhiệm vụ của chúng ta là tạo một Mảng bằng cách sử dụng các phần tử của mảng đã cho. Kích thước của mảng mới nên M và bất kỳ mảng con nào có kích thước lớn hơn K không được có tất cả các phần tử giống nhau. chúng ta phải in ra tổng lớn nhất có thể của mảng đã tạo.

Hãy lấy một ví dụ để hiểu vấn đề

Đầu vào - arr [] ={1, 2, 4, 5, 7}, M =5, K =2

Giải thích - mảng được tạo thỏa mãn điều kiện {7, 7, 5, 7, 7}. Ở đây, không mảng con nào có kích thước lớn hơn 2 có thể có tất cả các phần tử giống nhau.

Để giải quyết vấn đề này, chúng ta cần tạo một mảng bằng cách sử dụng phần tử có giá trị lớn nhất. Nhưng chúng ta không thể sử dụng phần tử max nhiều hơn k lần, vì vậy sau k lần, chúng ta sẽ phải sử dụng phần tử max thứ hai của mảng. Chèn giá trị lớn nhất một giây sau mỗi k giá trị lớn nhất trong mảng và tạo một mảng có độ dài M. Kết quả cuối cùng sẽ là tổng của tất cả các phần tử của mảng này.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#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;
}

Đầu ra

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