// [ 1 0 1 1 1 0 0 ] => [ 1 -1 1 1 1 -1 -1 ]
// Longest Subarray for sum = 0
// longest Subarray with equal number of zeros and one
#include<bits/stdc++.h>
using namespace std ;
int marLen(int a[], int n)
{
unordered_map<int, int> m ; vector <int> v ;
int pre_sum = 0 ; int res = 0 ; cout << "res = " ;
for(int i=0; i<n; i++){
pre_sum += a[i] ; v.push_back(pre_sum) ;
if(pre_sum == 0) res = i+1 ;
if(m.find(pre_sum) == m.end())
m.insert(make_pair(pre_sum, i)) ;
if(m.find(pre_sum) != m.end())
res = max(res, i-m[pre_sum]) ;
cout << res << " " ;
} cout << endl ;
for(int x : v) cout << x << " " ;
cout << endl ;
return res ;
}
int main()
{
int n ; cin >> n ; int a[n] = {0} ;
for(int i=0; i<n; i++) cin >> a[i] ;
for(int i=0; i<n; i++){
if(!a[i]) a[i] = -1 ;
}
cout << marLen(a, n) << endl ;
return 0 ;
}
/* Input -- 7
1 0 1 1 1 0 0
res = 0 2 2 2 2 2 6
1 0 1 2 3 2 1
6
*/
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter