Elija la suma máxima M elementos de modo que las repeticiones contiguas no excedan K

Dada una array arr[] de elementos distintos y dos enteros M y K , la tarea es generar una array a partir de los elementos de array dados (los elementos pueden repetirse en la array generada) de modo que el tamaño de la array generada sea M y la longitud de cualquier subarreglo con todos los mismos elementos no debe exceder K . Imprime la suma máxima de los elementos entre todos los arreglos posibles que se pueden generar.
Ejemplos: 
 

Entrada: arr[] = {1, 3, 6, 7, 4, 5}, M = 9, K = 2 
Salida: 60 
El arreglo de suma máxima es 7 7 6 7 7 6 7 7 6. Tenga en cuenta que no hay subarreglo de tamaño superior a 2 con todos los mismos elementos.
Entrada: arr[] = {8, 13, 9, 17, 4, 12}, M = 5, K = 1 
Salida: 77 
El arreglo de suma máxima es 17, 13, 17, 13, 17 
 

Enfoque: si queremos la suma máxima, debemos tomar el valor máximo de la array, pero podemos repetir este valor máximo como máximo K veces, por lo que debemos separarlo por el segundo valor máximo solo una vez y luego tomamos nuevamente el primer valor máximo. a K veces y este ciclo continúa hasta que tomamos M valores totales.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum required sum
long int maxSum(int arr[], int n, int m, int k)
{
 
    int max1 = -1, max2 = -1;
 
    // All the elements in the array are distinct
    // Finding the maximum and the second maximum
    // element from the array
    for (int i = 0; i < n; i++) {
        if (arr[i] > max1) {
            max2 = max1;
            max1 = arr[i];
        }
        else if (arr[i] > max2)
            max2 = arr[i];
    }
 
    // Total times the second maximum element
    // will appear in the generated array
    int counter = m / (k + 1);
 
    long int sum = counter * max2 + (m - counter) * max1;
 
    // Return the required sum
    return sum;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 3, 6, 7, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 9, k = 2;
    cout << maxSum(arr, n, m, k);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the maximum required sum
static int maxSum(int arr[], int n, int m, int k)
{
 
    int max1 = -1, max2 = -1;
 
    // All the elements in the array are distinct
    // Finding the maximum and the second maximum
    // element from the array
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > max1)
        {
            max2 = max1;
            max1 = arr[i];
        }
        else if (arr[i] > max2)
            max2 = arr[i];
    }
 
    // Total times the second maximum element
    // will appear in the generated array
    int counter = m / (k + 1);
 
    int sum = counter * max2 + (m - counter) * max1;
 
    // Return the required sum
    return sum;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 1, 3, 6, 7, 4, 5 };
    int n = arr.length;
    int m = 9, k = 2;
    System.out.println(maxSum(arr, n, m, k));
}
}
 
// This code is contributed by
// Surendra Gangwar

# Python3 implementation of the approach
def maxSum(arr, n, m, k):
 
    max1 = -1
    max2 = -1
     
    # All the elements in the array are distinct
    # Finding the maximum and the second maximum
    # element from the array
    for i in range(0, n):
        if(arr[i] > max1):
            max2 = max1
            max1 = arr[i]
        elif(arr[i] > max2):
            max2 = arr[i]
     
    # Total times the second maximum element
    # will appear in the generated array
    counter = int(m / (k + 1))
     
    sum = counter * max2 + (m - counter) * max1
     
    # Return the required sum
    return int(sum)
 
# Driver code
arr = [1, 3, 6, 7, 4, 5]
n = len(arr)
m = 9
k = 2
 
print(maxSum(arr, n, m, k))

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the maximum required sum
static int maxSum(int []arr, int n, int m, int k)
{
 
    int max1 = -1, max2 = -1;
 
    // All the elements in the array are distinct
    // Finding the maximum and the second maximum
    // element from the array
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > max1)
        {
            max2 = max1;
            max1 = arr[i];
        }
        else if (arr[i] > max2)
            max2 = arr[i];
    }
 
    // Total times the second maximum element
    // will appear in the generated array
    int counter = m / (k + 1);
 
    int sum = counter * max2 + (m - counter) * max1;
 
    // Return the required sum
    return sum;
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 1, 3, 6, 7, 4, 5 };
    int n = arr.Length;
    int m = 9, k = 2;
    Console.WriteLine(maxSum(arr, n, m, k));
}
}
 
/* This code contributed by PrinciRaj1992 */

<script>
 
// JavaScript implementation of the approach
 
// Function to return the maximum required sum
function maxSum(arr, n, m, k)
{
 
    var max1 = -1, max2 = -1;
 
    // All the elements in the array are distinct
    // Finding the maximum and the second maximum
    // element from the array
    for (var i = 0; i < n; i++) {
        if (arr[i] > max1) {
            max2 = max1;
            max1 = arr[i];
        }
        else if (arr[i] > max2)
            max2 = arr[i];
    }
 
    // Total times the second maximum element
    // will appear in the generated array
    var counter = m / (k + 1);
 
    var sum = counter * max2 + (m - counter) * max1;
 
    // Return the required sum
    return sum;
}
 
// Driver code
var arr = [1, 3, 6, 7, 4, 5];
var n = arr.length;
var m = 9, k = 2;
document.write( maxSum(arr, n, m, k));
 
 
</script>

60

Complejidad de tiempo: O(n), donde n es el tamaño de la array dada.
Espacio auxiliar: O(1), no se utiliza espacio adicional.