edited by
12,383 views
49 votes
49 votes

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

  1. maximum possible sum of elements in any sub-array of array E.
  2. maximum element in any sub-array of array E.
  3. sum of the maximum elements in all possible sub-arrays of array E.
  4. the sum of all the elements in the array E.
edited by

5 Answers

Best answer
47 votes
47 votes

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;  
}

 

edited by
5 votes
5 votes

 

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

2 votes
2 votes

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.
1 votes
1 votes
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.
edited by
Answer:

Related questions

89 votes
89 votes
16 answers
2
go_editor asked Sep 28, 2014
53,622 views
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
34 votes
34 votes
4 answers
4
go_editor asked Sep 26, 2014
12,116 views
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjac...