Cuente los subarreglos máximos que no se superponen con la suma dada

Dada una array arr[] que consta de N enteros y un objetivo entero , la tarea es encontrar el número máximo de subarreglos no vacíos que no se superponen de modo que la suma de los elementos de la array en cada subarreglo sea igual al objetivo .

Ejemplos:

Entrada: arr[] = {2, -1, 4, 3, 6, 4, 5, 1}, target = 6
Salida: 3
Explicación: 
Subarreglos {-1, 4, 3}, {6} y {5, 1} tiene una suma igual al objetivo (= 6).

Entrada: arr[] = {2, 2, 2, 2, 2}, objetivo = 4
Salida: 2 

Enfoque: para obtener los subarreglos más pequeños que no se superpongan con el objetivo de la suma , el objetivo es utilizar la técnica Prefix Sum . Siga los pasos a continuación para resolver el problema:

1. Almacene todas las sumas calculadas hasta el momento en un Map mp con clave como la suma del prefijo hasta ese índice y valor como el índice final del subarreglo con esa suma.
2. Si el prefijo-sum hasta el índice i , digamos sum , es igual a target , verifique si sum – target existe en el Mapa o no.
3. Si sum – target existe en Map y mp[sum – target] = idx , significa que el subarreglo de [idx + 1, i] tiene sum igual a target .
4. Ahora, para los subarreglos que no se superponen, mantenga una variable disponible adicional (establecida inicialmente en -1) y tome el subarreglo de [idx + 1, i] solo cuando mp[sum – target] ≥ aproveIdx .
5. Cada vez que se encuentre tal subarreglo, incremente la respuesta y cambie el valor de AvailabilityIdx al índice actual.
6. Además, para los subarreglos que no se superponen, siempre es beneficioso tomar con avidez los subarreglos lo más pequeños posible. Entonces, para cada prefijo-suma encontrado, actualice su índice en el Mapa, incluso si ya existe.
7. Imprima el valor de conteo después de completar los pasos anteriores.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count maximum number
// of non-overlapping subarrays with
// sum equals to the target
int maximumSubarrays(int arr[], int N,
                     int target)
{
    // Stores the final count
    int ans = 0;
 
    // Next subarray should start
    // from index >= availIdx
    int availIdx = -1;
 
    // Tracks the prefix sum
    int cur_sum = 0;
 
    // Map to store the prefix sum
    // for respective indices
    unordered_map<int, int> mp;
    mp[0] = -1;
 
    for (int i = 0; i < N; i++) {
 
        cur_sum += arr[i];
 
        // Check if cur_sum - target is
        // present in the array or not
        if (mp.find(cur_sum - target)
                != mp.end()
            && mp[cur_sum - target]
                   >= availIdx) {
 
            ans++;
            availIdx = i;
        }
 
        // Update the index of
        // current prefix sum
        mp[cur_sum] = i;
    }
 
    // Return the count of subarrays
    return ans;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 2, -1, 4, 3,
                  6, 4, 5, 1 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given sum target
    int target = 6;
 
    // Function Call
    cout << maximumSubarrays(arr, N,
                             target);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count maximum number
// of non-overlapping subarrays with
// sum equals to the target
static int maximumSubarrays(int arr[], int N,
                            int target)
{
     
    // Stores the final count
    int ans = 0;
 
    // Next subarray should start
    // from index >= availIdx
    int availIdx = -1;
 
    // Tracks the prefix sum
    int cur_sum = 0;
 
    // Map to store the prefix sum
    // for respective indices
    HashMap<Integer,
            Integer> mp = new HashMap<Integer,
                                      Integer>();
    mp.put(0, 1);
 
    for(int i = 0; i < N; i++)
    {
        cur_sum += arr[i];
 
        // Check if cur_sum - target is
        // present in the array or not
        if (mp.containsKey(cur_sum - target) &&
            mp.get(cur_sum - target) >= availIdx)
        {
            ans++;
            availIdx = i;
        }
         
        // Update the index of
        // current prefix sum
        mp.put(cur_sum, i);
    }
 
    // Return the count of subarrays
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    int arr[] = { 2, -1, 4, 3,
                  6, 4, 5, 1 };
 
    int N = arr.length;
 
    // Given sum target
    int target = 6;
 
    // Function call
    System.out.print(maximumSubarrays(arr, N,
                                      target));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to count maximum number
# of non-overlapping subarrays with
# sum equals to the target
def maximumSubarrays(arr, N, target):
     
    # Stores the final count
    ans = 0
 
    # Next subarray should start
    # from index >= availIdx
    availIdx = -1
 
    # Tracks the prefix sum
    cur_sum = 0
 
    # Map to store the prefix sum
    # for respective indices
    mp = {}
    mp[0] = -1
 
    for i in range(N):
        cur_sum += arr[i]
 
        # Check if cur_sum - target is
        # present in the array or not
        if ((cur_sum - target) in mp and
          mp[cur_sum - target] >= availIdx):
            ans += 1
            availIdx = i
 
        # Update the index of
        # current prefix sum
        mp[cur_sum] = i
 
    # Return the count of subarrays
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 2, -1, 4, 3,
            6, 4, 5, 1 ]
 
    N = len(arr)
 
    # Given sum target
    target = 6
 
    # Function call
    print(maximumSubarrays(arr, N, target))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to count maximum number
// of non-overlapping subarrays with
// sum equals to the target
static int maximumSubarrays(int []arr, int N,
                            int target)
{
  // Stores the readonly count
  int ans = 0;
 
  // Next subarray should start
  // from index >= availIdx
  int availIdx = -1;
 
  // Tracks the prefix sum
  int cur_sum = 0;
 
  // Map to store the prefix sum
  // for respective indices
  Dictionary<int,
             int> mp = new Dictionary<int,
                                      int>();
  mp.Add(0, 1);
 
  for(int i = 0; i < N; i++)
  {
    cur_sum += arr[i];
 
    // Check if cur_sum - target is
    // present in the array or not
    if (mp.ContainsKey(cur_sum - target) &&
        mp[cur_sum - target] >= availIdx)
    {
      ans++;
      availIdx = i;
    }
 
    // Update the index of
    // current prefix sum
    if(mp.ContainsKey(cur_sum))
      mp[cur_sum] = i;
    else
      mp.Add(cur_sum, i);
  }
 
  // Return the count of subarrays
  return ans;
}
 
// Driver Code
public static void Main(String[] args)
{   
  // Given array []arr
  int []arr = {2, -1, 4, 3,
               6, 4, 5, 1};
   
  int N = arr.Length;
 
  // Given sum target
  int target = 6;
 
  // Function call
  Console.Write(maximumSubarrays(arr, N,
                                 target));
}
}
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program for the above approach
 
// Function to count maximum number
// of non-overlapping subarrays with
// sum equals to the target
function maximumSubarrays(arr, N, target)
{
    // Stores the final count
    var ans = 0;
 
    // Next subarray should start
    // from index >= availIdx
    var availIdx = -1;
 
    // Tracks the prefix sum
    var cur_sum = 0;
 
    // Map to store the prefix sum
    // for respective indices
    var mp = new Map();
    mp.set(0, 1);
 
    for (var i = 0; i < N; i++) {
 
        cur_sum += arr[i];
 
        // Check if cur_sum - target is
        // present in the array or not
        if (mp.has(cur_sum - target)
            && mp.get(cur_sum - target)
                   >= availIdx) {
 
            ans++;
            availIdx = i;
        }
 
        // Update the index of
        // current prefix sum
        mp.set(cur_sum , i);
    }
 
    // Return the count of subarrays
    return ans;
}
 
// Driver Code
 
// Given array arr[]
var arr = [2, -1, 4, 3,
              6, 4, 5, 1];
var N = arr.length;
 
// Given sum target
var target = 6;
 
// Function Call
document.write( maximumSubarrays(arr, N,
                         target));
 
</script>

3

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