Dado un arreglo arr[] que consta de N enteros y un entero K , la tarea es encontrar un subarreglo de tamaño K con la suma máxima y el recuento de elementos distintos igual al del arreglo original.
Ejemplos:
Entrada: arr[] = {7, 7, 2, 4, 2, 7, 4, 6, 6, 6}, K = 6
Salida: 31
Explicación: La array dada consta de 4 elementos distintos, es decir, {2, 4 , 6, 7}. El subarreglo de tamaño K que consta de todos estos elementos y la suma máxima es {2, 7, 4, 6, 6, 6} que comienza desde el quinto índice ( indexación basada en 1 ) del arreglo original.
Por lo tanto, la suma del subarreglo = 2 + 7 + 4 + 6 + 6 + 6 = 31.Entrada: arr[] = {1, 2, 5, 5, 19, 2, 1}, K = 4
Salida: 27
Enfoque ingenuo: el enfoque simple es generar todos los subarreglos posibles de tamaño K y verificar si tiene los mismos elementos distintos que el arreglo original. En caso afirmativo, encuentre la suma de este subarreglo. Después de verificar todos los subarreglos, imprima la suma máxima de todos esos subarreglos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// distinct elements present in the array
int distinct(int arr[], int n)
{
map<int,int> mpp;
// Insert all elements into the Set
for (int i = 0; i < n; i++)
{
mpp[arr[i]] = 1;
}
// Return the size of set
return mpp.size();
}
// Function that finds the maximum
// sum of K-length subarray having
// same unique elements as arr[]
int maxSubSum(int arr[], int n,int k, int totalDistinct)
{
// Not possible to find a
// subarray of size K
if (k > n)
return 0;
int maxm = 0, sum = 0;
for (int i = 0; i < n - k + 1; i++)
{
sum = 0;
// Initialize Set
set<int> st;
// Calculate sum of the distinct elements
for (int j = i; j < i + k; j++)
{
sum += arr[j];
st.insert(arr[j]);
}
// If the set size is same as the
// count of distinct elements
if ((int) st.size() == totalDistinct)
// Update the maximum value
maxm = max(sum, maxm);
}
return maxm;
}
// Driver code
int main()
{
int arr[] = { 7, 7, 2, 4, 2,
7, 4, 6, 6, 6 };
int K = 6;
int N = sizeof(arr)/sizeof(arr[0]);
// Stores the count of distinct elements
int totalDistinct = distinct(arr, N);
cout << (maxSubSum(arr, N, K, totalDistinct));
return 0;
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to count the number of
// distinct elements present in the array
static int distinct(int arr[], int n)
{
Set<Integer> set = new HashSet<>();
// Insert all elements into the Set
for (int i = 0; i < n; i++) {
set.add(arr[i]);
}
// Return the size of set
return set.size();
}
// Function that finds the maximum
// sum of K-length subarray having
// same unique elements as arr[]
static int maxSubSum(int arr[], int n,
int k,
int totalDistinct)
{
// Not possible to find a
// subarray of size K
if (k > n)
return 0;
int max = 0, sum = 0;
for (int i = 0; i < n - k + 1; i++) {
sum = 0;
// Initialize Set
Set<Integer> set = new HashSet<>();
// Calculate sum of the distinct elements
for (int j = i; j < i + k; j++) {
sum += arr[j];
set.add(arr[j]);
}
// If the set size is same as the
// count of distinct elements
if (set.size() == totalDistinct)
// Update the maximum value
max = Math.max(sum, max);
}
return max;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 7, 7, 2, 4, 2,
7, 4, 6, 6, 6 };
int K = 6;
int N = arr.length;
// Stores the count of distinct elements
int totalDistinct = distinct(arr, N);
System.out.println(
maxSubSum(arr, N, K, totalDistinct));
}
}
Python3
# Python3 program for the above approach
# Function to count the number of
# distinct elements present in the array
def distinct(arr, n):
mpp = {}
# Insert all elements into the Set
for i in range(n):
mpp[arr[i]] = 1
# Return the size of set
return len(mpp)
# Function that finds the maximum
# sum of K-length subarray having
# same unique elements as arr[]
def maxSubSum(arr, n, k, totalDistinct):
# Not possible to find a
# subarray of size K
if (k > n):
return 0
maxm = 0
sum = 0
for i in range(n - k + 1):
sum = 0
# Initialize Set
st = set()
# Calculate sum of the distinct elements
for j in range(i, i + k, 1):
sum += arr[j]
st.add(arr[j])
# If the set size is same as the
# count of distinct elements
if (len(st) == totalDistinct):
# Update the maximum value
maxm = max(sum, maxm)
return maxm
# Driver code
if __name__ == '__main__':
arr = [ 7, 7, 2, 4, 2, 7, 4, 6, 6, 6 ]
K = 6
N = len(arr)
# Stores the count of distinct elements
totalDistinct = distinct(arr, N)
print(maxSubSum(arr, N, K, totalDistinct))
# This code is contributed by ipg2016107
C#
// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to count the number of
// distinct elements present in the array
static int distinct(int[] arr, int n)
{
HashSet<int> set = new HashSet<int>();
// Insert all elements into the Set
for (int i = 0; i < n; i++) {
set.Add(arr[i]);
}
// Return the size of set
return set.Count;
}
// Function that finds the maximum
// sum of K-length subarray having
// same unique elements as arr[]
static int maxSubSum(int[] arr, int n,
int k,
int totalDistinct)
{
// Not possible to find a
// subarray of size K
if (k > n)
return 0;
int max = 0, sum = 0;
for (int i = 0; i < n - k + 1; i++) {
sum = 0;
// Initialize Set
HashSet<int> set = new HashSet<int>();
// Calculate sum of the distinct elements
for (int j = i; j < i + k; j++) {
sum += arr[j];
set.Add(arr[j]);
}
// If the set size is same as the
// count of distinct elements
if (set.Count == totalDistinct)
// Update the maximum value
max = Math.Max(sum, max);
}
return max;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 7, 7, 2, 4, 2,
7, 4, 6, 6, 6 };
int K = 6;
int N = arr.Length;
// Stores the count of distinct elements
int totalDistinct = distinct(arr, N);
Console.WriteLine(
maxSubSum(arr, N, K, totalDistinct));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of
// distinct elements present in the array
function distinct(arr, n)
{
var mpp = new Map();
// Insert all elements into the Set
for (var i = 0; i < n; i++)
{
mpp.set(arr[i], 1);
}
// Return the size of set
return mpp.size;
}
// Function that finds the maximum
// sum of K-length subarray having
// same unique elements as arr[]
function maxSubSum(arr, n,k, totalDistinct)
{
// Not possible to find a
// subarray of size K
if (k > n)
return 0;
var maxm = 0, sum = 0;
for (var i = 0; i < n - k + 1; i++)
{
sum = 0;
// Initialize Set
var st = new Set();
// Calculate sum of the distinct elements
for (var j = i; j < i + k; j++)
{
sum += arr[j];
st.add(arr[j]);
}
// If the set size is same as the
// count of distinct elements
if ( st.size == totalDistinct)
// Update the maximum value
maxm = Math.max(sum, maxm);
}
return maxm;
}
// Driver code
var arr = [7, 7, 2, 4, 2,
7, 4, 6, 6, 6];
var K = 6;
var N = arr.length;
// Stores the count of distinct elements
var totalDistinct = distinct(arr, N);
document.write(maxSubSum(arr, N, K, totalDistinct));
// This code is contributed by itsok.
</script>
Producción:
31
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es hacer uso de Map . Siga los pasos a continuación para resolver el problema:
- Recorra la array una vez y siga actualizando la frecuencia de los elementos de la array en el Mapa .
- Compruebe si el tamaño del mapa es igual al número total de elementos distintos presentes en la array original o no. Si se encuentra que es cierto, actualice la suma máxima.
- Mientras recorre la array original, si el i -ésimo recorrido cruza K elementos en la array, actualice el mapa eliminando una ocurrencia del (i – K) -ésimo elemento.
- Después de completar los pasos anteriores, imprima la suma máxima obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to count the number of
// distinct elements present in the array
int distinct(vector<int>arr, int N)
{
set<int> st;
// Insert array elements into set
for(int i = 0; i < N; i++)
{
st.insert(arr[i]);
}
// Return the st size
return st.size();
}
// Function to calculate maximum
// sum of K-length subarray having
// same unique elements as arr[]
int maxSubarraySumUtil(vector<int>arr, int N,
int K, int totalDistinct)
{
// Not possible to find an
// subarray of length K from
// an N-sized array, if K > N
if (K > N)
return 0;
int mx = 0;
int sum = 0;
map<int, int> mp;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update the mp
mp[arr[i]] += 1;
sum += arr[i];
// If i >= K, then decrement
// arr[i-K] element's one
// occurrence
if (i >= K)
{
mp[arr[i - K]] -= 1;
sum -= arr[i - K];
// If frequency of any
// element is 0 then
// remove the element
if (mp[arr[i - K]] == 0)
mp.erase(arr[i - K]);
}
// If mp size is same as the
// count of distinct elements
// of array arr[] then update
// maximum sum
if (mp.size() == totalDistinct)
mx = max(mx, sum);
}
return mx;
}
// Function that finds the maximum
// sum of K-length subarray having
// same number of distinct elements
// as the original array
void maxSubarraySum(vector<int>arr,
int K)
{
// Size of array
int N = arr.size();
// Stores count of distinct elements
int totalDistinct = distinct(arr, N);
// Print maximum subarray sum
cout<<maxSubarraySumUtil(arr, N, K, totalDistinct);
}
// Driver Code
int main()
{
vector<int>arr { 7, 7, 2, 4, 2,
7, 4, 6, 6, 6 };
int K = 6;
// Function Call
maxSubarraySum(arr, K);
}
// This code is contributed by ipg2016107
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to count the number of
// distinct elements present in the array
static int distinct(int arr[], int N)
{
Set<Integer> set = new HashSet<>();
// Insert array elements into Set
for (int i = 0; i < N; i++) {
set.add(arr[i]);
}
// Return the Set size
return set.size();
}
// Function to calculate maximum
// sum of K-length subarray having
// same unique elements as arr[]
static int maxSubarraySumUtil(
int arr[], int N, int K,
int totalDistinct)
{
// Not possible to find an
// subarray of length K from
// an N-sized array, if K > N
if (K > N)
return 0;
int max = 0;
int sum = 0;
Map<Integer, Integer> map
= new HashMap<>();
// Traverse the array
for (int i = 0; i < N; i++) {
// Update the map
map.put(arr[i],
map.getOrDefault(arr[i], 0) + 1);
sum += arr[i];
// If i >= K, then decrement
// arr[i-K] element's one
// occurrence
if (i >= K) {
map.put(arr[i - K],
map.get(arr[i - K]) - 1);
sum -= arr[i - K];
// If frequency of any
// element is 0 then
// remove the element
if (map.get(arr[i - K]) == 0)
map.remove(arr[i - K]);
}
// If map size is same as the
// count of distinct elements
// of array arr[] then update
// maximum sum
if (map.size() == totalDistinct)
max = Math.max(max, sum);
}
return max;
}
// Function that finds the maximum
// sum of K-length subarray having
// same number of distinct elements
// as the original array
static void maxSubarraySum(int arr[],
int K)
{
// Size of array
int N = arr.length;
// Stores count of distinct elements
int totalDistinct = distinct(arr, N);
// Print maximum subarray sum
System.out.println(
maxSubarraySumUtil(arr, N, K,
totalDistinct));
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 7, 7, 2, 4, 2,
7, 4, 6, 6, 6 };
int K = 6;
// Function Call
maxSubarraySum(arr, K);
}
}
Python3
# Python 3 program for the above approach
# Function to count the number of
# distinct elements present in the array
def distinct(arr, N):
st = set()
# Insert array elements into set
for i in range(N):
st.add(arr[i])
# Return the st size
return len(st)
# Function to calculate maximum
# sum of K-length subarray having
# same unique elements as arr[]
def maxSubarraySumUtil(arr, N, K, totalDistinct):
# Not possible to find an
# subarray of length K from
# an N-sized array, if K > N
if (K > N):
return 0
mx = 0
sum = 0
mp = {}
# Traverse the array
for i in range(N):
# Update the mp
if(arr[i] in mp):
mp[arr[i]] += 1
else:
mp[arr[i]] = 1
sum += arr[i]
# If i >= K, then decrement
# arr[i-K] element's one
# occurrence
if (i >= K):
if(arr[i-K] in mp):
mp[arr[i - K]] -= 1
sum -= arr[i - K]
# If frequency of any
# element is 0 then
# remove the element
if (arr[i-K] in mp and mp[arr[i - K]] == 0):
mp.remove(arr[i - K])
# If mp size is same as the
# count of distinct elements
# of array arr[] then update
# maximum sum
if (len(mp) == totalDistinct):
mx = max(mx, sum)
return mx
# Function that finds the maximum
# sum of K-length subarray having
# same number of distinct elements
# as the original array
def maxSubarraySum(arr, K):
# Size of array
N = len(arr)
# Stores count of distinct elements
totalDistinct = distinct(arr, N)
# Print maximum subarray sum
print(maxSubarraySumUtil(arr, N, K, totalDistinct))
# Driver Code
if __name__ == '__main__':
arr = [7, 7, 2, 4, 2,7, 4, 6, 6, 6]
K = 6
# Function Call
maxSubarraySum(arr, K)
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to count the number of
// distinct elements present in the array
static int distinct(List<int>arr, int N)
{
HashSet<int> st = new HashSet<int>();
// Insert array elements into set
for(int i = 0; i < N; i++)
{
st.Add(arr[i]);
}
// Return the st size
return st.Count;
}
// Function to calculate maximum
// sum of K-length subarray having
// same unique elements as arr[]
static int maxSubarraySumUtil(List<int>arr, int N,
int K, int totalDistinct)
{
// Not possible to find an
// subarray of length K from
// an N-sized array, if K > N
if (K > N)
return 0;
int mx = 0;
int sum = 0;
Dictionary<int,int> mp = new Dictionary<int,int>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update the mp
if(mp.ContainsKey(arr[i]))
mp[arr[i]] += 1;
else
mp[arr[i]] = 1;
sum += arr[i];
// If i >= K, then decrement
// arr[i-K] element's one
// occurrence
if (i >= K)
{
if(mp.ContainsKey(arr[i - K]))
mp[arr[i - K]] -= 1;
else
mp[arr[i - K]] = 1;
sum -= arr[i - K];
// If frequency of any
// element is 0 then
// remove the element
if (mp[arr[i - K]] == 0)
mp.Remove(arr[i - K]);
}
// If mp size is same as the
// count of distinct elements
// of array arr[] then update
// maximum sum
if (mp.Count == totalDistinct)
mx = Math.Max(mx, sum);
}
return mx;
}
// Function that finds the maximum
// sum of K-length subarray having
// same number of distinct elements
// as the original array
static void maxSubarraySum(List<int>arr,
int K)
{
// Size of array
int N = arr.Count;
// Stores count of distinct elements
int totalDistinct = distinct(arr, N);
// Print maximum subarray sum
Console.WriteLine(maxSubarraySumUtil(arr, N, K, totalDistinct));
}
// Driver Code
public static void Main()
{
List<int>arr = new List<int>{ 7, 7, 2, 4, 2,
7, 4, 6, 6, 6 };
int K = 6;
// Function Call
maxSubarraySum(arr, K);
}
}
// This code is contributed by bgangwar59.
Javascript
<script>
// JavaScript program for the above approach
// Function to count the number of
// distinct elements present in the array
function distinct(arr, N)
{
var st = new Set();
// Insert array elements into set
for(var i = 0; i < N; i++)
{
st.add(arr[i]);
}
// Return the st size
return st.size;
}
// Function to calculate maximum
// sum of K-length subarray having
// same unique elements as arr[]
function maxSubarraySumUtil(arr, N, K, totalDistinct)
{
// Not possible to find an
// subarray of length K from
// an N-sized array, if K > N
if (K > N)
return 0;
var mx = 0;
var sum = 0;
var mp = new Map();
// Traverse the array
for(var i=0; i<N; i++)
{
// Update the mp
if(mp.has(arr[i]))
mp.set(arr[i], mp.get(arr[i])+1)
else
mp.set(arr[i], 1)
sum += arr[i];
// If i >= K, then decrement
// arr[i-K] element's one
// occurrence
if (i >= K)
{
if(mp.has(arr[i-K]))
mp.set(arr[i-K], mp.get(arr[i-K])-1)
sum -= arr[i - K];
// If frequency of any
// element is 0 then
// remove the element
if (mp.has(arr[i - K]) && mp.get(arr[i - K])== 0)
mp.delete(arr[i - K]);
}
// If mp size is same as the
// count of distinct elements
// of array arr[] then update
// maximum sum
if (mp.size == totalDistinct)
mx = Math.max(mx, sum);
}
return mx;
}
// Function that finds the maximum
// sum of K-length subarray having
// same number of distinct elements
// as the original array
function maxSubarraySum(arr, K)
{
// Size of array
var N = arr.length;
// Stores count of distinct elements
var totalDistinct = distinct(arr, N);
// Print maximum subarray sum
document.write( maxSubarraySumUtil(arr, N, K, totalDistinct));
}
// Driver Code
var arr = [7, 7, 2, 4, 2,
7, 4, 6, 6, 6 ];
var K = 6;
// Function Call
maxSubarraySum(arr, K);
</script>
Producción:
31
Complejidad temporal: O(N)
Espacio auxiliar: O(N)