[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum

[srinivas karlapudi]

this is 'Maximum Subsequence Problem'
i saw solutions of orders of n(3),n(2),nlongn,n
in DataStructures and Algo. Analysis by Mark Allen Weiss.

srinivasOn 1/25/06, Hemanth <[EMAIL PROTECTED]> wrote:
Well,Here's a solution :Create an array of cumulative sums i.e. cs[i]  = sum of elements fromindex 0 to iNow, find the maximum cumulative sum index say 'y'. We can excludeelements after index 'y' since they do not contribute positively to the
cumulative sum.Also, let 'x' be the minimum cumulative sum point. Then we can ignorenumbers from 0 to x (inlcuding x) since they do not contribute to thecumulative sum.So, the indices of the sub-array with the maximal sum should be (x+1,
y)Thanks,Hemanth

[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum

[Hemanth]

Well,

Here's a solution :
Create an array of cumulative sums i.e. cs[i]  = sum of elements from
index 0 to i

Now, find the maximum cumulative sum index say 'y'. We can exclude
elements after index 'y' since they do not contribute positively to the
cumulative sum.

Also, let 'x' be the minimum cumulative sum point. Then we can ignore
numbers from 0 to x (inlcuding x) since they do not contribute to the
cumulative sum.

So, the indices of the sub-array with the maximal sum should be (x+1,
y) 

Thanks,
Hemanth

[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum

[Arvind Sharma]

This will not work when you have a negative number in the resultant subarray.
If n=3 and a={ 7, -4,  25}. 
Returns 25,2,2 while the correct answer is 28,0,2 
Your algo assumes that if the current element is negative it cannot appear in the final list. Correct?Regards,
Arvind.
 
On 1/21/06, algorithm <[EMAIL PROTECTED]
> wrote: 
Here is my  code :- //O(n) complexityvoid largest_subarray(int* a, int n, int* sum, int *start_index, int* 
end_index){   int maxX=0, maxY=0, maxsum=a[0];   int tmpX=0,tmpY=0,tmpsum=a[0];   int i;   for (i=1; i   {  if (tmpsum > 0 && a[i] > 0)  {   tmpY = i; 
   tmpsum += a[i];  }  else  {   tmpX = tmpY = i;   tmpsum = a[i];  }  if (tmpsum > maxsum)  { maxsum = tmpsum; maxX = tmpX; 
 maxY = tmpY;  }   }   *start_index = maxX;   *end_index = maxY;   *sum = maxsum;}

[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum

[ricky]

Think of the negative numbers as consumers from a warehouse and
positive numbers as producers from the warehouse. The problem reduces
to plotting the inventory (starting from time = 0 to time = n) and then
finding the max amplitude over time axis in +ve quadrant of the
inventory profile which can be done in O(n).

[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum

[algorithm]

Here is my  code :- //O(n) complexity

void largest_subarray(int* a, int n, int* sum, int *start_index, int*
end_index)
{
int maxX=0, maxY=0, maxsum=a[0];
int tmpX=0,tmpY=0,tmpsum=a[0];
int i;

for (i=1; i 0 && a[i] > 0)
   {
tmpY = i;
tmpsum += a[i];
   }
   else
   {
tmpX = tmpY = i;
tmpsum = a[i];
   }

   if (tmpsum > maxsum)
   {
  maxsum = tmpsum;
  maxX = tmpX;
  maxY = tmpY;
   }
}
*start_index = maxX;
*end_index = maxY;
*sum = maxsum;
}

[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum

[GBY]

First, using a matrix to store the value of a[i][j] is unnecessary,if a
array s[] is used to store the summation of first i elements of A[],
that is s[i] = A[1] + ... +A[i], which means a[i][j] = s[j] - s[i - 1].
Second, computing "max" costs O(n) by using s[], The problem becomes to
find a interval which achieves the max value, that is to find a proper
upper bond i and a lower bond j. The most tricky thing which leads the
algorithm to O(n) is when you scan each i j from 1 to n, you never
return.
hope it helps :)