Consider the following C function in which size is the number of elements in…
2014
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.
Attempted by 83 students.
Show answer & explanation
Correct answer: A
Answer: The function returns the maximum possible sum of elements in any contiguous sub-array of E.
Why: The code first computes the sum of the entire array and stores it in Y. The nested loops then enumerate every contiguous sub-array (from index i to j), compute its sum Z, and update Y whenever Z is larger than the current Y. Because the full array is one of these contiguous sub-arrays, the final Y is the largest sum found among all contiguous sub-arrays.
First loop (for i = 0..size-1): computes Y = sum of all elements (total array sum).
Nested loops (for i, for j = i..size-1, inner loop for k = i..j): compute Z = sum of elements from i to j for every contiguous sub-array and set Y = Z if Z > Y.
Since the full array (i = 0, j = size-1) is included among these sub-arrays, Y ends up as the maximum contiguous sub-array sum.
Edge case: When all elements are negative, the algorithm still finds the largest (least negative) contiguous sub-array sum because single-element sub-arrays are considered; the result is not forced to be non-negative.
Complexity: Time complexity is O(n^3) in the given implementation (three nested loops for general sizes). The result (maximum contiguous sub-array sum) can be computed more efficiently in O(n) using Kadane's algorithm.
Example: For E = [-5, 10, -1, 10], the total sum is 14 but the maximum contiguous sub-array sum is 19 (from sub-array [10, -1, 10]); the function returns 19.