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 <learner....@gmail.com> 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 < > > > > richi.sankalp1...@gmail.com> 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 algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
