top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Subarray which has maximum sum.

+5 votes
521 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 by Diya Sharma

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
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.

2 Answers

+3 votes
    int sequence(int a[],int n,int i,int s,int b[],int *sum,int j)
    {
            if(s==n)
                    return 0;
            int add=0,k;

            for(k=i;k<=n-s+j;k++)
            {
                    //printf("%d+",a[k]);=add+a[k];
            }

            if(add > *sum)
            {
                    *sum = add;
                    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;
  }
answer Oct 12, 2013 by Vikas Upadhyay
0 votes

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.

answer Oct 12, 2013 by Salil Agrawal
Similar Questions
+8 votes

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.

+5 votes
      40
      /\
     20 60
     /\  \
   10 30  80
      /   /\
     25  70 90
           \
           75

longest path 
25 30 20 40 60 80 70 75 
Answer
    25 ----> 75
+3 votes

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

+7 votes

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

Answer

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
...