@ rajiv
but there are conditions that sum should be positive and greater than
zero... so just reversing sign wont work..
On Fri, Feb 4, 2011 at 12:22 AM, Rajiv Podar <rajeevpo...@gmail.com> wrote:
> @ Snehal,
>
> Yes you are right, I wrote function for finding max sub array. It can be
> converted to find min sub array by just switching the comparison operator :)
>
>
>
> On Fri, Feb 4, 2011 at 12:14 AM, snehal jain <learner....@gmail.com>wrote:
>
>> @ Above
>> u r finding maximum sum subarray
>>
>> whereas question is asking for minimum
>>
>> On Thu, Feb 3, 2011 at 11:34 PM, Rajiv Podar <rajeevpo...@gmail.com>wrote:
>>
>>> Hi Richi,
>>>
>>> Thanks for finding the problem. I forgot to add one condition:
>>> Please have a look on the following code. I hope this will solve the
>>> problem.
>>>
>>> int array[] = {-1,-2,3,4};
>>> int length = 4;
>>>
>>> int max = 0;
>>> int current = 0;
>>>
>>> for (int i = 0; i < length; i++)
>>> {
>>> current += array[i];
>>> if (current < 0 )
>>> {
>>> current = 0;
>>> }
>>> max = max > current ? max : current;
>>> }
>>> std::cout<<"Max is : "<<max;
>>>
>>>
>>>
>>> Thanks & Regards,
>>> Ricky
>>>
>>>
>>>
>>> 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<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<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<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.
