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