Author |
Topic: Maximum Subarray with equal no of 1s and 0s (Read 6458 times) |
|
KWillets
Junior Member
Posts: 84
|
 |
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #25 on: Mar 23rd, 2010, 6:06pm » |
 Quote  Modify
|
It's fairly easy to keep a running sum of +1 and -1 for 0,1 respectively, and look for the widest pair of equal values. Sums are bounded by -n, n, so space and time are O(n).
Pseudo code:
| hidden: |
int sum[n];
int firstOcc[ -n, n ] (initialize to -1's);
int running = 0;
int maxwidth = 0;
int maxval = 0;
for( i=0; i < n; i++ ) {
running += (a[i] == 0) ? -1 : 1 ;
sum[i] = running;
if( firstOcc[running] == -1 )
firstOcc[running] = i;
else if( i - firstOcc[running] > maxwidth ) {
maxwidth = i - firstOcc[running];
maxval = i; // location of pair
}
}
print firstOcc[ sum[maxval]], maxval;
|
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #26 on: Mar 24th, 2010, 2:56am » |
Quote Modify
|
Such a shame we only have constant extra space to work with.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #27 on: Mar 24th, 2010, 11:07pm » |
Quote Modify
|
Ah yes.
If the original array can be overwritten with int's, I believe we can overwrite each a[i] with the first index j where sum[j] == i. If the sums are always positive this works; it may be possible to adjust the range for negative values as well (the total range can't be more than n).
While we're iterating we just keep looking up a[sum[j]] and either setting it to j or checking j-a[sum[j]] for maximality.
I also have a scheme for in-place backpointers (to equal values of sum) that might work.
|
|
IP Logged |
|
|
|
byte
Newbie
Posts: 1
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #28 on: Apr 3rd, 2010, 4:28pm » |
Quote Modify
|
This is my first post. I apologize if the code doesn't appear formatted as it looks OK with white spaces in my code editor but I am finding it a bit difficult to post formatted code here.
| hidden: | Code:int MaxSubArrayWithEqual0and1(int arr[], int arrLen, int &start, int &end)
{
int len = arrLen; // Len of array
int i = 0;
int SumOfArray = 0; // Total sum of the array
int TotalOnes = 0;
int TotalZeroes = 0;
// Calculate sum of array, total number of 1s and 0s
for (i = 0; i < len; i++)
{
SumOfArray += arr[i];
if ( arr[i] == 0 )
{
TotalZeroes ++;
}
}
TotalOnes = len - TotalZeroes;
int extras = 0;
if(TotalZeroes == arrLen || TotalOnes == arrLen)
{
return FALSE;
}
if(TotalZeroes > TotalOnes) // Zeroes are more
{
extras = TotalZeroes - TotalOnes;
}
else if(TotalZeroes < TotalOnes) // Ones are more
{
extras = TotalOnes - TotalZeroes;
}
else
{
start = 0; end = arrLen-1;
return TRUE;
}
start = end = 0;
if(TotalZeroes > TotalOnes) // Zeroes are more
{
for ( i = 0; i < len ; i++)
{
if(arr[i] == 0)
{
start ++;
TotalZeroes--;
}
else if (arr[i] == 1)
{
start --;
TotalOnes --;
}
if( (0 == TotalOnes) && (extras >= TotalZeroes) )
{
end = i;
break;
}
}
}
else
{
for ( i = 0; i < len ; i++)
{
if(arr[i] == 0)
{
start --;
TotalZeroes--;
}
else if (arr[i] == 1)
{
start ++;
TotalOnes --;
}
if( (0 == TotalZeroes) && (extras >= TotalOnes) )
{
end = i;
break;
}
}
}
return TRUE;
}
int _tmain(int argc, _TCHAR* argv[])
{
// int arr[] = {0, 0, 1, 1, 1, 0, 0, 0, 0};
// int arr[] = {0, 0, 0, 0, 1, 1, 1, 0, 0};
// int arr[] = {0, 0, 0, 0, 1, 1, 0, 1, 0, 0};
int arr[] = {1, 1, 0, 0, 0, 1, 1, 1, 1};
//int arr[] = {1, 1, 1, 1, 0, 0, 0, 1, 1};
int arrLen = sizeof(arr)/sizeof(arr[0]);
int start = 0;
int end = 0;
MaxSubArrayWithEqual0and1(arr, arrLen, start, end);
return 0;
}
|
|
|
|
| « Last Edit: Apr 3rd, 2010, 4:33pm by byte » |
IP Logged |
|
|
|
kirru
Newbie
Posts: 34
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #29 on: Apr 8th, 2010, 5:49am » |
Quote Modify
|
so finally what is the summary about this discussion??
|
|
IP Logged |
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #30 on: Apr 8th, 2010, 9:48am » |
Quote Modify
|
Till now we have 0(N) solution with O(N) space. Still we are trying to find a 0(N) solution with constant space.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print