GATE CSE 2014 Set 1 | Question: 41

Question

Consider the following C function in which size is the number of elements in the array E: 

int MyX(int *E, unsigned int size) 
{ 
   int Y = 0; 
   int Z; 
   int i, j, k; 

   for(i = 0; i< size; i++) 
          Y = Y + E[i]; 
          
    for(i=0; i < size; i++) 
        for(j = i; j < size; j++)
        {
            Z = 0; 
            for(k = i; k <= j; k++) 
               Z = Z + E[k];
            if(Z > Y) 
               Y = Z; 
        } 
   return Y; 
} 

The value returned by the function MyX is the

• A. maximum possible sum of elements in any sub-array of array E.
• B. maximum element in any sub-array of array E.
• C. sum of the maximum elements in all possible sub-arrays of array E.
• D. the sum of all the elements in the array E.

Comments

palashbehra5

LOL!😂

---

HOW DO WE GET THAT WE HAVE TO CONSIDER NEGATIVE NUMBERS IN ARRAY?

Ans: Function name hints xD

---

Itarative approach to understand 

Answer 1

Answer is (A) maximum possible sum of elements in any sub-array of array E.

int MyX ( int * E, unsigned int size )
{
    int Y= 0;
    int z;
    int i, j,k;
   
//calculate sum of the elements of the array E and stores it in Y
    for i 0;i<size;i++)   
      Y = Y+E[i]; 
      
//calculate the sum of all possible subaarays 
//(starting from postion 0..n-1)  
    for (i=0;i<size;i++)        
        for(j=i;j<size ;j++)       
        {                                    
            z = 0;                    
            for(k=i; k<=j;k++)  
                z=z+E[k]; 
                
//checks whether sum of elements of each subarray is greater
//than the current max, if so, then assign it to currentmax
            if(z>Y)           
                Y = z;
        }
//ultimately returns the maximum possible sum of elements 
//in any sub array of given array E    
    return Y;  
}

 

Comments

The sum of all the elements is always going to be greater than any sub array. So, the output of the code will always be the total sum of the array. Right?

---

Can anybody take an example and solve this question ?

---

You always increase my thinking level,thanks a lot sir @Arjun

Answer 2

 

here, you clearly see that y is updated when sub-array elements 3,1,5 sum is maximum.

So the function returns the maximum possible sum of elements in any sub-array of the array E.

 

Answer : A

Comments

Why did you include negative number in the array??

---

in question, nothing is mentioned about elements of the array, whatever your wish you will take (positive or negative or combination of both).

Answer 3

Y = sum of all elements (initially)

Z = sum of subarrays

Y>Z = sum of subarrays that exceed the overall max

doing Y=Z is finding overall max value that could occur in a subarray

 

Scenarios : 

1. If array has all positive elements, then each Z will always be less than Y , Z<Y is always the case
2. If array has “x” number of zeros. If these zeros are present anywhere , then again Z<Y holds only; if these zeros are towards the extreme left or extreme right, then Y=Z can occur.
3. If array even has negative elements, then Y<Z or Y=Z or Y>Z all these can occur. So, overall in such an array, you really see the effect, and you’ll get a subarray of max value in Y.

Answer 4

The function does following Y is used to store maximum sum seen so far and Z is used to store current sum

1) Initialize Y as sum of all elements

2) For every element, calculate sum of all subarrays starting with arr[i]. Store the current sum in Z. If Z is greater than Y, then update Y.