Subarray which has maximum sum.

205 views
``````An array of positive and negative number is given.
Find out the subarray which have maximum sum.

Input =>  1   -2   5   -9    4    11    3    -9
Output =>  4, 11,  3    SUM = 18

Input =>    1    -4    5     9    -1     -9    19     9    0    5    -11   -10   38
Output =>   5, 9, -1, -9 ,19, 9, 0, 5, -11, -10, 38       sum = 54
``````
posted Oct 12, 2013

Can u clarify the question further, this looks very cryptic to me. Do you mean sub-array will have only consecutive members.
Subarray  means part of array (consecutive elements ).
I have given the example too.
Thats what my doubt, I got the question.

``````    int sequence(int a[],int n,int i,int s,int b[],int *sum,int j)
{
if(s==n)
return 0;

for(k=i;k<=n-s+j;k++)
{
}

{
b[0] = i;
b[1] = n-s+j;
}
s++;

for(k=0,j=0;k<s;k++,i++,j++)
sequence(a,n,i,s,b,sum,j);
}

int main()
{
int a[20],b[2];
int i,sum,n;
sum=0;
printf("Enter theno of element in sequence => ");
scanf("%d",&n);

printf("\nEnter the sequence element => ");
for(i=0;i<n;i++)
{
printf("\nEnter the element %d = ",i+1);
scanf("%d",&a[i]);
}
sequence(a,n,0,1,b,&sum,0);

printf("\n\nSum of largst sequence => %d\nindex %d to %d\n\n",sum,b[0],b[1]);

return 0;
}
``````

The solution could be vary similar to bubble sort

``````Steps
1. choose max_sum as -ve infinity.
2. for i = 1 to size of array
for j=0 to (size of array - i)
{
sum = 0;
for k=0 to (i-1)
sum += array_element [ j + k]
if sum > max_sum
then replace max_sum with sum.
3. Return max_sum
``````

But this is not the best algo.

Similar Questions

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

``````      40
/\
20 60
/\  \
10 30  80
/   /\
25  70 90
\
75

longest path
25 30 20 40 60 80 70 75
25 ----> 75
``````

Input: arr[] = {5, 5, 10, -10, -20, 40, 50, 35, -20, -50}
Output: 125 (40, 50, 35)

You have a 2D matrix. Only two ZEROs in matrix.
Find the path from 1st zero to 2nd zero with least sum.

``````1       6       8       9       0       3

4       9       -5      5       11      13

8       9       44      23      15      -20

7       9       7       -13     14      11

0       16      23      31      16      7

67      5       4       23      21      19
``````

``````1       6       8       9       0  ----> 3