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