The Gateway to Computer Science Excellence

+33 votes

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.**

+39 votes

Best answer

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; }

+1

Your second definition is correct for subarray. And int *E actually means a pointer to int. But in C language using a pointer we can access adjacent locations and this is how an array is passed to a function in C.

0

sir then this question program doesnt calculate the maximum sum of any subarray?

because it doesnt consider the other permutations. i.e. those subarrays which do not start from first element

because it doesnt consider the other permutations. i.e. those subarrays which do not start from first element

+1

Is it clear now? The code is considering all subarrays - starting from each position and of all sizes.

+6

I am not able to get one thing...

How can a sum of subarray(Z) , can ever be greater than sum of all elements (Y) in array... ?

How can a sum of subarray(Z) , can ever be greater than sum of all elements (Y) in array... ?

+1

I also have the similar doubt as Arunav Khare. How can sum of sub-array be greater than the complete array?

0

@Arjun

// calculate sum of the elements of the array E and stores it in Y

for i 0;i<size;i++)

Y = Y+E[i];

first for loop has some syntax problem .

Time complexity will be O(n^{4} ) ryt? sir

0

Sir,I run the program using array={-1,10,-2,-3,15} .

It will return 20

As nowhere subarray (1,4) is checked

Please correct me if I wrong

It will return 20

As nowhere subarray (1,4) is checked

Please correct me if I wrong

0

Nishan subarray(1,4) is checked when value of i=1,j=4*(after 3 iteration of j, that is j=i=1 then j=2 then j=3 then j=4*). then the max. value 20 is achieved.

0

Even i have the same doubt,cause this part of the function will never be executed.

I agree that this program is supposed to print maximum possible sum of elements in any sub array but logically no array will have an subarray other than array itself where sum of the subarray is greater than sum of array.

I agree that this program is supposed to print maximum possible sum of elements in any sub array but logically no array will have an subarray other than array itself where sum of the subarray is greater than sum of array.

+1 vote

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.

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.

0 votes

+21

You have considered all elements of the array to be positive... what if there is negative number as well in the array?? So can't then any subarray which have more sum than the whole..?? It can be, if we avoid some negative numbers.. So (A) is correct...

+12

-5 | 8 | -7 | 6 | 9 |

sum of each element of array is 11

sub array last two element's sum is 15 .

clear ??????

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,832 questions

57,686 answers

199,273 comments

107,204 users