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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
