oh sorry.. i saved the complete ans in my draft and posted half ( as i got interrupted when i ws typing) and so sent incomplete reply,..
here is my complete solution. hope it works.. let me know..if it fails somewhere.. though i have tried it... on some test cases Given Input Array A form the prefix sum array P of A. i.e P[i] = A[1] + A[2] + ... + A[i] Now create another array Q of pairs (Value, Index) such that Q[i].Value = P[i]. Q[i].Index = i Now sort that array Q, considering only Q[i].Value for comparison. We get a new sorted array Q' such that Q'[i].Value <= Q'[i+1].Value Now walk the array Q' and find the minimum positive value of Q'[i+1].Value - Q'[i].Value, considering only those i for which Q'[i+1].Index > Q'[i].Index Time complexity o( nlogn) On Thu, Feb 3, 2011 at 6:58 PM, sankalp srivastava < [email protected]> wrote: > @above guy with cheers and all and snehal > > the best way to prove wrong is by a test case , so , > > -1 -2 3 4 > > Ricky's solution will give the answer as 4 , while the answer is 7 > > @snehal . > [quote]if indices starting at 1 > bothers you then take > > P[i]= A[0] + A[1] + .... + A[i] > its one and the same thing.. [\Quote] > I'm really not that stupid to bother about an off-by-one error :-) > Your algo rephrased :- > P[i] = A[1] + A[2] + … + A[i] > so , > P[1]=-1 > P[2]=-3 > P[3]=0 > P[4]=4 > > Q[i].Value = P[i]. > Q[i].Index = i > > So , > > Q[1]=-1 , 1 > Q[2]=-3 , 2 > Q[3]=0 , 3 > Q[4]=4 , 4 > > Now , as u said , let's sort it > > new Q={{4 , 4} ,{0 , 3} ,{-1 , 1} ,{-3 , 3}} > You din mention anything after this , so I dunnoe what you plan up > from here . How are we going to get the answer {3 , 4 } from here ? > > Now , > > > On Feb 2, 10:06 pm, Ricky <[email protected]> wrote: > > Hi you can try the following code snippet: > > int array[] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2}; > > int length = 10; > > > > int max = 0; > > int current = 0; > > > > for (int i = 0; i < length; i++) > > { > > current += array[i]; > > max = max > current ? max : current; > > } > > std::cout<<"Max is : "<<max; > > > > Cheers!!!!!!!!!! > > > > On Feb 2, 9:04 pm, snehal jain <[email protected]> wrote: > > > > > > > > > @ above > > > didnt get you? why is the solution wrong? and if indices starting at 1 > > > bothers you then take > > > > > P[i]= A[0] + A[1] + .... + A[i] > > > its one and the same thing.. > > > > > On Wed, Feb 2, 2011 at 6:02 PM, sankalp srivastava < > > > > > [email protected]> wrote: > > > > > > This solution is wrong , never has it been said that the indices will > > > > occur from 1.....i (if that is the case , you don't need to sort , > > > > just return the maximum /minimum sum obtained as a result) > > > > > > The indices were b/w i..j such that 1<=i<=j<=n > > > > > > O(n) solution does not exist .The state space tree will have n! leaf > > > > nodes(because there is some ordering on the input data , otherwise it > > > > would have 2^n leaf nodes) .Traversing the tree will take O(log n!) > > > > steps , or O(n log n) > > > > In fact a slight modification to this , the subset sum problem id NP- > > > > complete . > > > > But with the Q[i] array , you can get the answer with simple > recursion > > > > ( or bfs or state space search or dp ) . > > > > > > On Feb 2, 1:33 pm, snehal jain <[email protected]> wrote: > > > > > @ above > > > > > its nt any homework question.. i found it a good question... aftr > > > > spending a > > > > > lot of time i came up with following solution > > > > > > > Given Input Array A > > > > > > > form the prefix sum array P of A. > > > > > > > i.e P[i] = A[1] + A[2] + … + A[i] > > > > > > > Now create another array Q of pairs (Value, Index) > > > > > > > such that > > > > > > > Q[i].Value = P[i]. > > > > > Q[i].Index = i > > > > > > > Now sort that array Q, considering only Q[i].Value for comparison. > > > > > > > We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index > > > > > > > Time complexity o( nlogn) > > > > > > > and my O(n) which i posted earlier is giving incorrect result in > some > > > > > case..so ignore that.. > > > > > > > so does there exist O(n) solution for it also.. i had tried a lot > but > > > > could > > > > > not figure out. but i think it should exist as there is for the > other > > > > > variation.. > > > > > > > On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava < > > > > > > > [email protected]> wrote: > > > > > > > > You should not post homework problems . > > > > > > 1)For divide and conquer :- > > > > > > Read about interval trees , binary indexed trees , > segments > > > > > > trees . > > > > > > Solve this using interval tree (By the time you solve a few > > > > > > basic problems of interval tree , you would be able to figure out > a > > > > > > solution) > > > > > > > > the function to calculate the parent will be > > > > > > 1) first check if the two are +ve > > > > > > 2) if yes , join both of them and also iterate on the sides left > by > > > > > > both , to see if you can include them also (You only need to see > the > > > > > > positive elements , no negative elements ) > > > > > > > > T(n)=2T(n/2)+O(n) > > > > > > > > I gan explain in detail , please correct me if im wrong > > > > > > > > Logic :- Basically in the subproblem , we would have founded the > > > > > > maximum subarray in that well , subarray (short of words ) .So , > if we > > > > > > want to ,we can only increase the solution in the next subarray > (the > > > > > > second subproblem ) > > > > > > So , there will be three cases > > > > > > > > Either the subarray , the most minimum sum in one of the > subproblems > > > > > > will be the answer > > > > > > The answer will be from between the gap of the indices between > the > > > > > > solutions of the two subproblems > > > > > > The answer will be any combination of the two > > > > > > > > All these three can be checked in O(n) itself . > > > > > > > > 2)Using DP(I don't know how many dp (pure dp i mean) algorithms > are in > > > > > > O(nlog n) .Never heard of any with the pure dp approach and an n > log n > > > > > > solution ) > > > > > > > > DP(classical for maximum positive sum array ) can be done by > going > > > > > > through two loops > > > > > > > > dp[i]= minimum positive sum for an array with index (last index > =i ) > > > > > > p[i]= start index corresponding to this dp[i] > > > > > > > > dp[i]= minimum sum condition ( for each i<j ) > > > > > > update p[i] accordingly .Then return the minimum amongst dp[i] > and > > > > > > corresponding p[i] . > > > > > > > > This is a complete search , so I don't think it will get wrong . > > > > > > > > And i don't think it could be solved in O(n log n) (at least with > > > > > > dp) .Because the search space tree would be of height O(log n) > (with > > > > > > no overlapping problems ) and dp lives upon overlapping > subproblems . > > > > > > Or may be , if someone could provide with a O( n log n) solution > > > > > > > > Regards , > > > > > > Sankalp Srivastava > > > > > > > > "I live the way I type , fast and full of errors " > > > > > > > > -- > > > > > > 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]<algogeeks%[email protected]> > <algogeeks%2Bunsubscribe@googlegroups .com> > > > > <algogeeks%2Bunsubscribe@googlegroups .com> > > > > > > . > > > > > > For more options, visit this group at > > > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > > > > 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]<algogeeks%[email protected]> > <algogeeks%2Bunsubscribe@googlegroups .com> > > > > . > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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?hl=en.
