Chọn M phần tử có tổng lớn nhất sao cho lặp liên tiếp không vượt quá K trong C++

Trong bài toán này, chúng ta được cho mảng arr[] và hai số nguyên M và K. Nhiệm vụ là tạo một mảng mới sử dụng các phần tử của mảng cho trước. Kích thước mảng mới phải là M và bất kỳ mảng con nào có kích thước lớn hơn K không được phép 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 được tạo ra.

Ví dụ minh họa:

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

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

Để giải bài toán, chúng ta cần tạo mảng sử dụng phần tử có giá trị lớn nhất. Nhưng không thể dùng phần tử lớn nhất quá K lần, nên sau K lần phải dùng phần tử lớn thứ hai của mảng. Chèn một giá trị lớn thứ hai sau mỗi K giá trị lớn nhất trong mảng và tạo mảng độ dài M. Kết quả cuối cùng là tổng của tất cả các phần tử mảng này.

Chương trình minh họa

#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 << "Tổng lớn nhất của mảng tạo từ mảng cho trước sao cho không có mảng con kích thước lớn hơn " << k << " có cùng phần tử là "; 
    cout << arraySum(arr, n, m, k); 
    return 0; 
}

Kết quả

Tổng lớn nhất của mảng tạo từ mảng cho trước sao cho không có mảng con kích thước lớn hơn 2 có cùng phần tử là 60