@ above and the answer to your test case is not 7 its 4 only.. as we have to
find min sum...i think u r confusing between max sum and min sum..
On Thu, Feb 3, 2011 at 10:15 PM, snehal jain <learner....@gmail.com> wrote:
> 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 <
> richi.sankalp1...@gmail.com> 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 <rajeevpo...@gmail.com> 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 <learner....@gmail.com> 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 <
>> >
>> > > richi.sankalp1...@gmail.com> 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 <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%2bunsubscr...@googlegroups.com>
>> <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 algogeeks@googlegroups.com.
>> > > > To unsubscribe from this group, send email to
>> > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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.
