@Monsieur: Note that 0 is not positive so it doesn't match your stated
solution requirement. Maybe you meant "non-negative" instead of
"positive", or maybe you meant that the answer is 1, having sum=1.
Dave
On Feb 9, 10:42 am, MONSIEUR wrote:
> Given: An array of integers(may be both positive an
@sunny: actually it is not like maximum positive sum.it is
necessary to select at least one number.The only constraint is MINIMUM
POSITIVE SUM , If all numbers are negative then print simply "no
positive sum exist".
example: {-300,98,-230}
answer: 98
On Feb 9, 10:23 pm, sunny agrawal
@apaza: brute force.checking all combinations(with at least one
negative number,if any)..too hard buddy.
On Feb 9, 10:07 pm, Rel Guzman Apaza wrote:
> I think the only solution will be finding all subsets.
>
> 2011/2/9 MONSIEUR
>
> > @jalaj: text missing.??? I think i've mentione
in this question is it necessary to select atleast one element, else minimum
positive sum will be 0 for each case, by selecting zero numbers as this
question seems to be same as maximum positive sum in which if all elements
are negative, ans is zero that is by selecting zero no of elements ??
I think the only solution will be finding all subsets.
2011/2/9 MONSIEUR
> @jalaj: text missing.??? I think i've mentioned question
> properly.is there any thing more u require?
>
> n Feb 9, 9:45 pm, jalaj jaiswal wrote:
> > @monsieur ... text missing dude
> >
> >
> >
> > On Wed, Feb 9,
@jalaj: text missing.??? I think i've mentioned question
properly.is there any thing more u require?
n Feb 9, 9:45 pm, jalaj jaiswal wrote:
> @monsieur ... text missing dude
>
>
>
> On Wed, Feb 9, 2011 at 10:12 PM, MONSIEUR wrote:
> > Given: An array of integers(may be both positive and
@ 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 wrote:
> @ Snehal,
>
> Yes you are right, I wrote function for finding max sub array. It can be
> converted to find min sub array
@ 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 wrote:
> @ Above
> u r finding maximum sum subarray
>
> whereas question is asking for m
@ Above
u r finding maximum sum subarray
whereas question is asking for minimum
On Thu, Feb 3, 2011 at 11:34 PM, Rajiv Podar 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.
>
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 <
@ricky
u r also trying to find max sum subarray..
On Thu, Feb 3, 2011 at 10:18 PM, snehal jain wrote:
> @ 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
@ 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 wrote:
> oh sorry.. i saved the complete ans in my draft and posted half ( as i got
> interrupted when i ws
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
@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 thin
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 > curre
@ 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 be
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 wi
@ 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 =
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 fun
a try:
int minsum(int A[],int n)
{
int min=-1,cur=0,x1=0,x2=0,i;
for(i=0;i0)
{
min=A[i];
break;
}
}
if(i==n&&min==-1)
return min;
for(i=0;icur-A[x1]&&i!=x1) {
cur=cur-A[x1];
x1=x1+1;
}
if(cur< min && cur>0)
{
x2=i;
min=c
@nishanth
oh ya right..
On Sun, Jan 30, 2011 at 11:27 AM, nishaanth wrote:
> @snehalno 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 jai
@snehalno 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 wrote:
> a friend of mine was asked this question in google interview..
>
> according to
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 h
On Jan 21, 1:05 am, snehal jain 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, a
24 matches
Mail list logo