The GATE Grind

GATE 2014 CS (CS1) – Question 51

Programming and Data Structures · Arrays · 2 marks · Multiple choice

Consider this C function, where size is the number of elements in E:

int MyX(int *E, unsigned int size) {
int Y = 0, Z, 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;
}

What does MyX return?

  1. Maximum possible sum of elements in any subarray of E
  2. Maximum element in any subarray of E
  3. Sum of the maximum elements in all possible subarrays of E
  4. Sum of all elements in E

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Maximum possible sum of elements in any subarray of E

Explanation

The nested i,j loops enumerate every nonempty contiguous subarray, and the k loop computes its sum. Y starts as the full-array sum and is replaced whenever a larger subarray sum is found. Therefore the function returns the **maximum subarray sum,A**, assuming a nonempty array and no integer overflow.