a try:
int minsum(int A[],int n)
{
int min=-1,cur=0,x1=0,x2=0,i;
for(i=0;i<n;i++)
{if(A[i]>0)
{
min=A[i];
break;
}
}
if(i==n&&min==-1)
return min;
for(i=0;i<n;i++)
{
cur =cur + A[i];
if(cur>cur-A[x1]&&i!=x1) {
cur=cur-A[x1];
x1=x1+1;
}
if(cur< min && cur>0)
{
x2=i;
min=cur;
}
}
return min;
}
please correct me if the logic is incorrect..
On Sun, Jan 30, 2011 at 12:22 PM, snehal jain <[email protected]> wrote:
> @nishanth
> oh ya right..
>
>
>
> On Sun, Jan 30, 2011 at 11:27 AM, nishaanth <[email protected]> wrote:
>
>> @snehal....no its incorrect..consider the following example
>> -2 3
>>
>> The answer to this problem is the entire array with sum 1.(not the min of
>> positive number)
>>
>>
>>
>> On Sun, Jan 30, 2011 at 11:00 AM, snehal jain <[email protected]>wrote:
>>
>>> a friend of mine was asked this question in google interview..
>>>
>>> according to me the min element in the array is the answer provided that
>>> its not zero.. as 1 element can also be a subarray. but that would solve the
>>> problem in O(n) only.. ( this is what i understood) am i missing anything..?
>>> please help..
>>>
>>>
>>> On Sun, Jan 30, 2011 at 5:19 AM, Dan <[email protected]> wrote:
>>>
>>>> On Jan 21, 1:05 am, snehal jain <[email protected]> wrote:
>>>> > In this variation of the Maximum-Sum Subarray Problem, you are given a
>>>> > one-dimensional array A[1 : n] of positive or negative numbers, and
>>>> > you are asked to find a subarray A[i : j] such that the sum of its
>>>> > elements is (1) strictly greater than zero, and (2) minimum. In other
>>>> > words, you want to find a subarray of smallest positive sum. Give an
>>>> > O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic
>>>> > Programming Algorithm.
>>>>
>>>> There are three considerations here:
>>>>
>>>> 1) Insufficient clarity in the problem statement.
>>>> 2) Most people don't want to do others homework/school problems for
>>>> them.
>>>> 3) At very least... you need to show that you are attempting to
>>>> answer the problem yourself at least a little bit.
>>>>
>>>> --
>>>> 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%[email protected]>
>>>> .
>>>> 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%[email protected]>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> S.Nishaanth,
>> Computer Science and engineering,
>> IIT Madras.
>>
>> --
>> 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%[email protected]>
>> .
>> 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.
