Dada una array arr[] y un entero K , la tarea es imprimir el número máximo de subarreglos que no se superponen con una suma igual a K .
Ejemplos:
Entrada: arr[] = {-2, 6, 6, 3, 5, 4, 1, 2, 8}, K = 10 Salida: 3
Explicación :
Todos los posibles subarreglos no superpuestos con suma K(= 10) son { -2, 6, 6}, {5, 4, 1}, {2, 8}. Por lo tanto, el conteo requerido es 3.Entrada: arr[] = {1, 1, 1}, K = 2
Salida: 1
Enfoque: el problema se puede resolver utilizando el concepto de suma de prefijos . Siga los pasos a continuación para resolver el problema:
- Inicializa un conjunto para almacenar todas las sumas de prefijos obtenidas hasta el elemento actual.
- Inicialice las variables prefixSum y res , para almacenar la suma del prefijo del subarreglo actual y el recuento de subarreglos con una suma igual a K respectivamente.
- Itere sobre la array y para cada elemento de la array, actualice prefixSum agregándole el elemento actual. Ahora, verifique si el valor prefixSum – K ya está presente en el conjunto o no. Si se determina que es cierto, incremente res , borre el conjunto y restablezca el valor de prefixSum .
- Repita los pasos anteriores hasta que se atraviese toda la array. Finalmente, imprima el valor de res.
C++14
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the maximum
// number of subarrays with sum K
int CtSubarr(int arr[], int N, int K)
{
// Stores all the distinct
// prefixSums obtained
unordered_set<int> st;
// Stores the prefix sum
// of the current subarray
int prefixSum = 0;
st.insert(prefixSum);
// Stores the count of
// subarrays with sum K
int res = 0;
for (int i = 0; i < N; i++) {
prefixSum += arr[i];
// If a subarray with sum K
// is already found
if (st.count(prefixSum - K)) {
// Increase count
res += 1;
// Reset prefix sum
prefixSum = 0;
// Clear the set
st.clear();
st.insert(0);
}
// Insert the prefix sum
st.insert(prefixSum);
}
return res;
}
// Driver Code
int main()
{
int arr[] = { -2, 6, 6, 3, 5, 4, 1, 2, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 10;
cout << CtSubarr(arr, N, K);
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Function to count the maximum
// number of subarrays with sum K
static int CtSubarr(int[] arr,
int N, int K)
{
// Stores all the distinct
// prefixSums obtained
Set<Integer> st = new HashSet<Integer>();
// Stores the prefix sum
// of the current subarray
int prefixSum = 0;
st.add(prefixSum);
// Stores the count of
// subarrays with sum K
int res = 0;
for (int i = 0; i < N; i++)
{
prefixSum += arr[i];
// If a subarray with sum K
// is already found
if (st.contains(prefixSum - K))
{
// Increase count
res += 1;
// Reset prefix sum
prefixSum = 0;
// Clear the set
st.clear();
st.add(0);
}
// Insert the prefix sum
st.add(prefixSum);
}
return res;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {-2, 6, 6, 3,
5, 4, 1, 2, 8};
int N = arr.length;
int K = 10;
System.out.println(CtSubarr(arr, N, K));
}
}
// This code is contributed by Chitranayal
Python3
# Python3 program to implement # the above approach # Function to count the maximum # number of subarrays with sum K def CtSubarr(arr, N, K): # Stores all the distinct # prefixSums obtained st = set() # Stores the prefix sum # of the current subarray prefixSum = 0 st.add(prefixSum) # Stores the count of # subarrays with sum K res = 0 for i in range(N): prefixSum += arr[i] # If a subarray with sum K # is already found if((prefixSum - K) in st): # Increase count res += 1 # Reset prefix sum prefixSum = 0 # Clear the set st.clear() st.add(0) # Insert the prefix sum st.add(prefixSum) return res # Driver Code arr = [ -2, 6, 6, 3, 5, 4, 1, 2, 8 ] N = len(arr) K = 10 # Function call print(CtSubarr(arr, N, K)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count the maximum
// number of subarrays with sum K
static int CtSubarr(int[] arr,
int N, int K)
{
// Stores all the distinct
// prefixSums obtained
HashSet<int> st = new HashSet<int>();
// Stores the prefix sum
// of the current subarray
int prefixSum = 0;
st.Add(prefixSum);
// Stores the count of
// subarrays with sum K
int res = 0;
for(int i = 0; i < N; i++)
{
prefixSum += arr[i];
// If a subarray with sum K
// is already found
if (st.Contains(prefixSum - K))
{
// Increase count
res += 1;
// Reset prefix sum
prefixSum = 0;
// Clear the set
st.Clear();
st.Add(0);
}
// Insert the prefix sum
st.Add(prefixSum);
}
return res;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { -2, 6, 6, 3,
5, 4, 1, 2, 8};
int N = arr.Length;
int K = 10;
Console.WriteLine(CtSubarr(arr, N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to count the maximum
// number of subarrays with sum K
function CtSubarr(arr, N, K)
{
// Stores all the distinct
// prefixSums obtained
var st = new Set();
// Stores the prefix sum
// of the current subarray
var prefixSum = 0;
st.add(prefixSum);
// Stores the count of
// subarrays with sum K
var res = 0;
for (var i = 0; i < N; i++) {
prefixSum += arr[i];
// If a subarray with sum K
// is already found
if (st.has(prefixSum - K)) {
// Increase count
res += 1;
// Reset prefix sum
prefixSum = 0;
// Clear the set
st = new Set();
st.add(0);
}
// Insert the prefix sum
st.add(prefixSum);
}
return res;
}
// Driver Code
var arr = [-2, 6, 6, 3, 5, 4, 1, 2, 8];
var N = arr.length;
var K = 10;
document.write( CtSubarr(arr, N, K));
// This code is contributed by importantly.
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array