Vivek, you did pretty good there. I tried solving it through dynamic programming but failed to find the optimal substructure.
_dufus On Aug 26, 9:57 pm, Vivek S <[email protected]> wrote: > let A[i+1] = a[0] + a[1] + ... + a[i]; > let B[i+1] = b[0] + b[1] + ... + b[i]; > A[0] = B[0] = 0; > sum of nos from i to j of a[] = A[j+1] - A[i]; // O(1) time > > Thus O(n^2) sol can be obtained for this problem by finding the sub-array > sum in the range [i, j] for every i, j; > But I have not used the fact that the given nos is either 0 or 1. > There should be a better way, yet to think about it :) > > 2009/8/26 ankur aggarwal <[email protected]> > > > Find longest interval We are given with two arrays A and B..each of size > > N...elements of array contains either 1 or 0... > > > we have to find such an interval (p,q)(inclusive) such that the sum of all > > the elements of A (between this interval) and sum of all elements of B > > (between this interval ) is equal... > > > i.e. > > > a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q] > > -- > "Reduce, Reuse and Recycle" > Regards, > Vivek.S --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
