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

Time Complexity is O(n^3) ...right?

---

Yes bro

---

Is it only me or someone else too found the name of the function funny?🤣

---

yes, MyX was complicated.

---

palashbehra5

LOL!😂

---

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

Ans: Function name hints xD

---

Itarative approach to understand 

---

for the first iterations

 where i=j=k=0 Z must be Z=0+1=1

 where i=j=k=1 Z must be Z=0+2=2

---

those who are confused why z is greater than y so array can contain positive and negative value also .....

---

Those who are confused , Well the function name itself is MyX ,
She will take max of all the qualties you had.☠️

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

but first we are summing all of array , and then finding the sum of sub-arrays

then obiously, the total sum of array is always greater than sub arrray!

like if a[] = 2,3,4

then total sum = 9 and it will always greater than it's sub array!!

---

@Aditya_np1 , what if the array elements contains negitive elements not all , then subarray can be greater than the total subarray

---

@Aditya_np1

let the array be :

E = [-2, 3, -1, 4]

• Sum of whole array (Y initially) = -2 + 3 - 1 + 4 = 4
• Sub-array [3, -1, 4] = 6 → greater than 4!
• Sub-array [4] alone = 4
• Sub-array [3] alone = 3

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

So by now everyone must have found out the answer is: 

A. maximum possible sum of elements in any sub-array of array E.

But I see alot of people having doubt why choose negative as it wasn't mentioned anywhere. So here is the answer for it. 

Lets assume you take all numbers as postive the 1st option would be applicable there as well as the option D, which is sum of all the elements because in case of all the elements are postivie it is always going to return sum of all the elements. (Sum of subarray cant be bigger than sum of all the elements) Now you might ask why option 1st will be applicable there: The answer for that is very simple 

The entire array can be considered a subarray of itself. A subarray is defined as a contiguous portion of an array, and since the entire array is contiguous, it qualifies as a subarray. So, if you have an array of size 𝑛, there is exactly one subarray that is the entire array.

Now you have 2 options that qualifies as a probable answer but that shouldn't be possible unless there is some issue with the question so that is when you think of negative int values as well. Which won't satisfy the option D. Hence A is the correct answer for all the test cases.

Hope this helps. 

Comments

nice explaination

Answer 5

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.

Answer 6

sum of subarray can never be greater than sum of all elements of an array .therefore ans is D

Comments

@kapilj123 NO UNSIGNED INT IS FOR SIZE NOT FOR NUMBER USED INSIDE ARRAY.....INSIDE ARRAY YOU CAN USE EITHER POSITIVE OR NEGATIVE ANY NUMBER .

---

saME

---

take negative element in the array and then think (Answer will be A)