GATE CS 2014 Set 1 Q.51 (CS Q.41): Data Types, Operators and Control Flow

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

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

maximum element in any sub-array of array E.

sum of the maximum elements in all possible sub-arrays of array E.

the sum of all the elements in the array E.

Official answer and solution

Official answer: A
From: Official GATE 2014 answer key

Solution

Trace the logic of the nested loops to see how sub-array sums are computed and tracked in variable Y.

In the function MyX:

The first loop calculates the sum of all elements in array E and stores it into Y: $Y = \sum_{i=0}^{\text{size}-1} E[i]$
The second set of loops has three indices:
- i ranges from $0$ to $\text{size}-1$ (starting index of sub-array).
- j ranges from i to $\text{size}-1$ (ending index of sub-array).
- k ranges from i to j, computing the sum of elements in the sub-array $E[i..j]$ and storing it into Z: $Z = \sum_{k=i}^j E[k]$
If $Z > Y$ , Y is updated to $Z$ .
Because all pairs $(i, j)$ with $0 \le i \le j < \text{size}$ are considered, every contiguous sub-array is examined.
The final value in Y is the maximum among the entire array sum and all sub-array sums, which is precisely the maximum possible sum of elements in any sub-array of array E.

Final answer

Common trap

Assuming the initial sum in Y forces the function to return only the full array sum, whereas subsequent sub-arrays can exceed it if negative numbers exist.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 1
Question: 51 of 65, printed as CS Q.41
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source