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
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 Correct Answer maximum possible sum of elements in any sub-array of array E
Concept:
Let’s take a small example
Array E, Size =4
|
4 |
3 |
2 |
1 |
Y = Sum of all elements = 10
|
Outer for loop i = 0 to i = 3 |
Inner for loop j = i to j = 3 |
Inner most for loop k = i to k = j |
|
i=0 |
j = 0 |
Z=0 K=0 to k=0 one time Z = 4 If( 4 > 10 )condition false |
|
i=0 |
j = 1 |
Z=0 and k=0 to k=1 Z=4+3=7 Condition false |
|
i = 0 |
j = 2 |
Z=0 and k=0 to k=2 and Z= 9 Condition false |
|
i = 0 |
j = 3 |
Z=0 and k=0 to k=3 and Z=10 Condition false |
After running outer loop one time we can observe here that every time it is calculating total sum of every sub array or maximum sum of that sub array then compare with Y. here you might confused with option 3. Option 3 is saying that in all sub array we are finding sum of maximum element (here maximum element word is important).
In program we are not finding maximum element in any sub array so option 3 is wrong option 1 is the correct answer.