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.
