/***
Input Array has both +ve and -ve ints.
Find the sub array with maximum sum.
Solution:
Run Time : O(n)
Assumes that whenever thisSum is less than 0 then we can get a better sum from the index following the current one.
***/
int maxSubSum3( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
int i=0;
int j=0;
while (j lessThan a.length)
{
if(a[j] lessThan 0)
{
thisSum = 0;
j++;
continue;
}
thisSum =thisSum + a[ j ];
if( thisSum greaterThan maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if( thisSum lessThan 0 )
{
i = j + 1;
thisSum = 0;
}
j=j+1;
}
return maxSum;
}
Other Solution
-10 8 -10 -12 -10
ReplyDeleteWhat you think will be the output?
8 should be the answer...
ReplyDeleteHi anonymous i edited the solution...hope this works now...
ReplyDeleteI appreciate your solution. But, i think it seems it doen't correctly tell the required indexes. removing the first if within the while statement will work correctly.
ReplyDeleteCheck this:
int[] nums = new int[] { 3, 2, 8, 9, -25, 5, 8, 4, 4, -3, 5, 3, -10 };
int startIndex = -2;
int endIndex = -2;
if (nums.Length > 0) //if there is at least one element
{
int maximumSum = 0;
int sequenceSum = 0;
int i = 0;
int j = 0;
while (j < nums.Length)
{
sequenceSum = sequenceSum + nums[j];
if (sequenceSum > maximumSum)
{
maximumSum = sequenceSum;
startIndex = i;
endIndex = j;
}
else if (sequenceSum < 0)
{
i = j + 1;
sequenceSum = 0;
}
j = j + 1;
}
}
Console.WriteLine("Start={0} and end={1}", startIndex, endIndex);
Your program does not work for something like this:-
ReplyDeleteint[] nums = new int[] { -1, -5, -6 };
can anyone explain me the problem statement even more descriptive..?pls??
ReplyDelete