ในปัญหานี้ เราได้รับอาร์เรย์ arr[] และจำนวนเต็ม M และ K สองจำนวน หน้าที่ของเราคือสร้างอาร์เรย์โดยใช้องค์ประกอบของอาร์เรย์ที่กำหนด ขนาดของอาร์เรย์ใหม่ควร M และอาร์เรย์ย่อยใดๆ ที่มีขนาดมากกว่า K ไม่สามารถมีองค์ประกอบทั้งหมดเหมือนกันได้ เราต้องพิมพ์ผลรวมสูงสุดที่เป็นไปได้โดยอาร์เรย์ที่สร้างขึ้น
มาดูตัวอย่างทำความเข้าใจปัญหากัน
ป้อนข้อมูล − arr[] ={1, 2, 4, 5, 7 }, M =5, K =2
คำอธิบาย − สร้างอาร์เรย์ที่ตรงตามเงื่อนไข {7, 7, 5, 7, 7} ในที่นี้ ไม่มีอาร์เรย์ย่อยที่มีขนาดมากกว่า 2 สามารถมีองค์ประกอบทั้งหมดที่เหมือนกันได้
เพื่อแก้ปัญหานี้ เราต้องสร้างอาร์เรย์โดยใช้องค์ประกอบที่มีค่าสูงสุด แต่เราไม่สามารถใช้องค์ประกอบสูงสุดมากกว่า k ครั้ง ดังนั้นหลังจาก k ครั้ง เราจะต้องใช้องค์ประกอบสูงสุดที่สองของอาร์เรย์ ใส่ค่าสูงสุดหนึ่งวินาทีหลังจากทุกค่า k max ในอาร์เรย์และสร้างอาร์เรย์ที่มีความยาว 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
