Maximice la suma de cada elemento elevado a la potencia de su frecuencia en un subarreglo de tamaño K

Dada una array arr[] de N elementos y un entero K . La tarea es encontrar la suma máxima de elementos en un subarreglo de tamaño K , con cada elemento elevado a la potencia de su frecuencia en el subarreglo.

Ejemplos:

Entrada: arr[] = { 2, 1, 2, 3, 3 }, N = 5, K = 3
Salida: 11
Explicación: Subarreglo requerido de tamaño 3 = {2, 3, 3}. La suma es 2 1 + 3 2 = 11, que es la suma máxima posible.

Entrada: arr[] = { 4, 9, 6, 5}, N = 4, K = 3
Salida: 20
Explicación: Los dos subarreglos de tamaño 3 son {4, 9, 6} y {9, 6, 5} . El subarreglo {9, 6, 5} tiene la suma = 20.

 

Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos. Luego, para cada subarreglo, cuente la frecuencia de los elementos y genere la suma. Ahora revisa las sumas para encontrar el máximo.

Complejidad temporal: O(N*K)
Espacio auxiliar: O(N*K)

Enfoque eficiente: un enfoque eficiente es utilizar el concepto de ventana deslizante para evitar generar todos los subarreglos. Luego, para cada ventana, cuente la frecuencia de los elementos en ella y descubra la suma. La suma máxima entre todas las ventanas es la respuesta.

Complejidad temporal: O(N*K)
Espacio auxiliar: O(K)

Enfoque más eficiente: esta idea también se basa en la técnica de la ventana deslizante. Pero en este enfoque se evita contar la frecuencia de cada elemento para cada ventana. Siga los pasos a continuación para implementar la idea:

  • Mantenga una ventana de tamaño K que denota el subarreglo.
  • Cuando la ventana cambia una posición a la derecha, reste la contribución del elemento inmediatamente a la izquierda de la ventana y el elemento más a la derecha de la ventana.
  • Ahora ajuste la frecuencia disminuyendo la frecuencia del elemento inmediatamente a la izquierda de la ventana e incrementando la frecuencia del elemento más a la derecha de la ventana.
  • Vuelva a agregar las contribuciones de acuerdo con las nuevas frecuencias de los elementos inmediatamente a la izquierda de la ventana y el elemento más a la derecha de la ventana.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ code to implement above approach
#include <bits/stdc++.h>
 
using namespace std;
#define mod 1000000007
 
// Function to find the maximum sum
// of a K sized subarray
long long int maxSum(vector<int>& arr,
                     int N, int K)
{
    long long int ans = 0;
 
    // Map to store frequency of elements
    // of the K sized subarray
    unordered_map<int, int> freq;
    for (int j = 0; j < K; j++) {
        freq[arr[j]]++;
    }
 
    long long int sum = 0;
 
    // Sum of the first K sized subarray
    for (auto m : freq)
        sum = (sum
               + ((long long int)
                  (pow(m.first, m.second)))
                     % mod)% mod;
     
    // Variable to store ans
    ans = max(ans, sum);
 
    for (int i = 1; i <= N - K; i++) {
        // Subtract the contribution of
        // the element immediately left
        // to the subarray
        sum -= freq[arr[i - 1]] > 0
                   ?
          ((long long int)
           (pow(arr[i - 1],
               freq[arr[i - 1]])))% mod
          : 0;
         
        // Update the frequency of
        // the element immediately left
        // to the subarray
        freq[arr[i - 1]]--;
         
        // Add back the contribution of
        // the element immediately left
        // to the subarray
        sum += freq[arr[i - 1]] > 0
                   ?
          ((long long int)
           (pow(arr[i - 1],
                freq[arr[i - 1]])))% mod
                   : 0;
 
        // Subtract the contribution of
        // the rightmost element
        // of the subarray
        sum -= freq[arr[i + K - 1]] > 0
                   ?
          ((long long int)
           (pow(arr[i + K - 1],
                freq[arr[i + K - 1]])))% mod
                   : 0;
 
        // Update the frequency of the
        // rightmost element of the subarray
        freq[arr[i + K - 1]]++;
         
        // Add back the contribution of the
        // rightmost element of the subarray
        sum += freq[arr[i + K - 1]] > 0
                   ?
          ((long long int)
           (pow(arr[i + K - 1],
                freq[arr[i + K - 1]])))% mod
                   : 0;
 
        // Update the answer
        ans = max(ans, sum);
    }
 
    return ans;
}
 
// Driver code
int main()
{
    // Declare the variable
    int N = 5, K = 3;
 
    vector<int> arr = { 2, 1, 2, 3, 3 };
 
    // Output the variable to STDOUT
    cout << maxSum(arr, N, K);
 
    return 0;
}

Java

// Java code to implement above approach
import java.util.ArrayList;
import java.util.HashMap;
 
class GFG {
    static int mod = 1000000007;
 
    // Function to find the maximum sum
    // of a K sized subarray
    static long maxSum(ArrayList<Integer> arr, int N, int K) {
        long ans = 0;
 
        // Map to store frequency of elements
        // of the K sized subarray
        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for (int j = 0; j < K; j++) {
            if (freq.containsKey(arr.get(j))) {
                freq.put(arr.get(j), freq.get(arr.get(j)) + 1);
            } else
                freq.put(arr.get(j), 1);
        }
 
        long sum = 0;
 
        // Sum of the first K sized subarray
        for (int m : freq.keySet()) {
            sum = (sum + ((long) (Math.pow(m, freq.get(m)))) % mod) % mod;
        }
 
        // Variable to store ans
        ans = Math.max(ans, sum);
 
        for (int i = 1; i <= N - K; i++) {
            // Subtract the contribution of
            // the element immediately left
            // to the subarray
            if (freq.containsKey(arr.get(i - 1))) {
                sum -= freq.get(arr.get(i - 1)) > 0
                        ? ((long) (Math.pow(
                                arr.get(i - 1),
                                freq.get(arr.get(i - 1)))))
                                % mod
                        : 0;
 
                // Update the frequency of
                // the element immediately left
                // to the subarray
                freq.put(arr.get(i - 1), freq.get(arr.get(i - 1)) - 1);
 
                // Add back the contribution of
                // the element immediately left
                // to the subarray
                sum += freq.get(arr.get(i - 1)) > 0
                        ? ((long) (Math.pow(
                                arr.get(i - 1),
                                freq.get(arr.get(i - 1)))))
                                % mod
                        : 0;
            }
            // Subtract the contribution of
            // the rightmost element
            // of the subarray
            if (freq.containsKey(arr.get(i + K - 1))) {
                sum -= freq.get(arr.get(i + K - 1)) > 0
                        ? ((long) (Math.pow(
                                arr.get(i + K - 1),
                                freq.get(arr.get(i + K - 1)))))
                                % mod
                        : 0;
            }
 
            // Update the frequency of the
            // rightmost element of the subarray
            if (freq.containsKey(arr.get(i + K - 1)))
                freq.put(arr.get(i + K - 1), freq.get(arr.get(i + K - 1)) + 1);
            else
                freq.put(arr.get(i + K - 1), 1);
 
            // Add back the contribution of the
            // rightmost element of the subarray
 
            sum += freq.get(arr.get(i + K - 1)) > 0
                    ? ((long) (Math.pow(
                            arr.get(i + K - 1),
                            freq.get(arr.get(i + K - 1)))))
                            % mod
                    : 0;
 
            // Update the answer
            ans = Math.max(ans, sum);
        }
        return ans;
    }
 
    // Driver code
    public static void main(String args[])
    {
       
        // Declare the variable
        int N = 5, K = 3;
 
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(2);
        arr.add(1);
        arr.add(2);
        arr.add(3);
        arr.add(3);
 
        // Output the variable to STDOUT
        System.out.println(maxSum(arr, N, K));
    }
}
 
// This code is contributed by Saurabh Jaiswal

Python3

# Python code for the above approach
mod = 1000000007
 
# Function to find the maximum sum
# of a K sized subarray
def maxSum(arr, N, K):
    ans = 0
 
    # Map to store frequency of elements
    # of the K sized subarray
    freq = [0] * 100001
    for j in range(K):
        freq[arr[j]] += 1
 
    sum = 0
 
    # Sum of the first K sized subarray
    for i in range(len(freq)):
        if (freq[i] != 0):
            sum += ((i ** freq[i]) % mod) % mod
 
    # Variable to store ans
    ans = max(ans, sum)
 
    for i in range(1, N - K + 1):
        # Subtract the contribution of
        # the element immediately left
        # to the subarray
        sum -= ((arr[i - 1] ** freq[arr[i - 1]])
                ) % mod if freq[arr[i - 1]] > 0 else 0
 
        # Update the frequency of
        # the element immediately left
        # to the subarray
        freq[arr[i - 1]] -= 1
 
        # Add back the contribution of
        # the element immediately left
        # to the subarray
        sum += ((arr[i - 1] ** freq[arr[i - 1]])
                ) % mod if freq[arr[i - 1]] > 0 else 0
 
        # Subtract the contribution of
        # the rightmost element
        # of the subarray
        sum -= ((arr[i + K - 1] ** freq[arr[i + K - 1]])
                ) % mod if freq[arr[i + K - 1]] > 0 else 0
 
        # Update the frequency of the
        # rightmost element of the subarray
        freq[arr[i + K - 1]] += 1
 
        # Add back the contribution of the
        # rightmost element of the subarray
        sum += ((arr[i + K - 1] ** freq[arr[i + K - 1]])
                ) % mod if freq[arr[i + K - 1]] > 0 else 0
 
        # Update the answer
        print("ans = ",ans, "sum = ",sum)
        ans = max(ans, sum)
 
    return ans
 
# Driver code
 
# Declare the variable
N = 5
K = 3
 
arr = [2, 1, 2, 3, 3]
 
print(maxSum(arr, N, K))
 
# This code is contributed by gfgking

C#

// C# code to implement above approach
using System;
using System.Collections.Generic;
class GFG {
  static int mod = 1000000007;
 
  // Function to find the maximum sum
  // of a K sized subarray
  static long maxSum(List<int> arr, int N, int K)
  {
    long ans = 0;
 
    // Map to store frequency of elements
    // of the K sized subarray
    Dictionary<int, int> freq
      = new Dictionary<int, int>();
    for (int j = 0; j < K; j++) {
      if (freq.ContainsKey(arr[j]))
        freq[arr[j]]++;
      else
        freq[arr[j]] = 1;
    }
 
    long sum = 0;
 
    // Sum of the first K sized subarray
    foreach(KeyValuePair<int, int> m in freq)
    {
      sum = (sum
             + ((long)(Math.Pow(m.Key, m.Value)))
             % mod)
        % mod;
    }
 
    // Variable to store ans
    ans = Math.Max(ans, sum);
 
    for (int i = 1; i <= N - K; i++) {
      // Subtract the contribution of
      // the element immediately left
      // to the subarray
      if (freq.ContainsKey(arr[i - 1])) {
        sum -= freq[arr[i - 1]] > 0
          ? ((long)(Math.Pow(
            arr[i - 1],
            freq[arr[i - 1]])))
          % mod
          : 0;
 
        // Update the frequency of
        // the element immediately left
        // to the subarray
        freq[arr[i - 1]]--;
 
        // Add back the contribution of
        // the element immediately left
        // to the subarray
        sum += freq[arr[i - 1]] > 0
          ? ((long)(Math.Pow(
            arr[i - 1],
            freq[arr[i - 1]])))
          % mod
          : 0;
      }
      // Subtract the contribution of
      // the rightmost element
      // of the subarray
      if (freq.ContainsKey(arr[i + K - 1])) {
        sum -= freq[arr[i + K - 1]] > 0
          ? ((long)(Math.Pow(
            arr[i + K - 1],
            freq[arr[i + K - 1]])))
          % mod
          : 0;
      }
 
      // Update the frequency of the
      // rightmost element of the subarray
      if (freq.ContainsKey(arr[i + K - 1]))
        freq[arr[i + K - 1]]++;
      else
        freq[arr[i + K - 1]] = 1;
 
      // Add back the contribution of the
      // rightmost element of the subarray
 
      sum += freq[arr[i + K - 1]] > 0
        ? ((long)(Math.Pow(
          arr[i + K - 1],
          freq[arr[i + K - 1]])))
        % mod
        : 0;
 
      // Update the answer
      ans = Math.Max(ans, sum);
    }
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    // Declare the variable
    int N = 5, K = 3;
 
    List<int> arr = new List<int>() { 2, 1, 2, 3, 3 };
 
    // Output the variable to STDOUT
    Console.WriteLine(maxSum(arr, N, K));
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
       // JavaScript code for the above approach
 
       let mod = 1000000007
 
       // Function to find the maximum sum
       // of a K sized subarray
       function maxSum(arr,
           N, K) {
           let ans = 0;
 
           // Map to store frequency of elements
           // of the K sized subarray
           let freq = new Array(100001).fill(0);
           for (let j = 0; j < K; j++) {
               freq[arr[j]]++;
           }
 
           let sum = 0;
 
           // Sum of the first K sized subarray
           for (let i = 0; i < freq.length; i++)
               if (freq[i] != 0) {
                   sum = (sum
                       + (
                           (Math.pow(i, freq[i])))
                       % mod) % mod;
               }
           // Variable to store ans
           ans = Math.max(ans, sum);
 
           for (let i = 1; i <= N - K; i++) {
               // Subtract the contribution of
               // the element immediately left
               // to the subarray
               sum -= freq[arr[i - 1]] > 0
                   ?
                   (
                       (Math.pow(arr[i - 1],
                           freq[arr[i - 1]]))) % mod
                   : 0;
 
               // Update the frequency of
               // the element immediately left
               // to the subarray
               freq[arr[i - 1]]--;
 
               // Add back the contribution of
               // the element immediately left
               // to the subarray
               sum += freq[arr[i - 1]] > 0
                   ?
                   (
                       (Math.pow(arr[i - 1],
                           freq[arr[i - 1]]))) % mod
                   : 0;
 
               // Subtract the contribution of
               // the rightmost element
               // of the subarray
               sum -= freq[arr[i + K - 1]] > 0
                   ?
                   (
                       (Math.pow(arr[i + K - 1],
                           freq[arr[i + K - 1]]))) % mod
                   : 0;
 
               // Update the frequency of the
               // rightmost element of the subarray
               freq[arr[i + K - 1]]++;
 
               // Add back the contribution of the
               // rightmost element of the subarray
               sum += freq[arr[i + K - 1]] > 0
                   ?
                   (
                       (Math.pow(arr[i + K - 1],
                           freq[arr[i + K - 1]]))) % mod
                   : 0;
 
               // Update the answer
               ans = Math.max(ans, sum);
           }
 
           return ans;
       }
 
       // Driver code
 
       // Declare the variable
       let N = 5, K = 3;
 
       let arr = [2, 1, 2, 3, 3];
 
        
       document.write(maxSum(arr, N, K));
 // This code is contributed by Potta Lokesh
   </script>
Producción

11

Complejidad temporal: O(N)
Espacio auxiliar: O(K)

Publicación traducida automáticamente

Artículo escrito por Code_r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *