3.6k views

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

1. maximum possible sum of elements in any sub-array of array E.
2. maximum element in any sub-array of array E.
3. sum of the maximum elements in all possible sub-arrays of array E.
4. the sum of all the elements in the array E.

edited | 3.6k views
+1
Time Complexity is O(n^3) ...right?
0
Yes bro

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

by Active (3.3k points)
edited
0

sub array means an array from a to a[k] k<n?

why shouldn't it be a[i] to a[j] i<j<=n?

0
and what does *E mean?

in this question?
+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
+1
Is it clear now? The code is considering all subarrays - starting from each position and of all sizes.
0
yes sir. just realised that. thanks
0
but array is declared as unsigned int then how it can carry negative values...??
+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... ?
+2

@Kalpana

Can you give an example, where below part will be true ?
if(z>Y)
Y = z;
+1

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

+35
@Monanshi When there are negative numbers.
0
@Arjun Thanks sir.
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(n4 ) 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
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.
0
The sum of all the elements is always going to be greater than any sub array. So, the output of the code will always be the total sum of the array. Right?
+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.
by Boss (10k points)
edited
sum of subarray can never be greater than sum of all elements of an array .therefore ans is D
by (331 points)
+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 ??????

0
Ans should be (D) because it is already given array is unsigned so we cant use negative numbers hence program will return sum of all elements which will always be maximum
+2
In the program its given that "unsigned int size"  it basically means the size of the array can't be negative...but here it doesn't means that the array may not contain negative values....so here the array may or maynot contain negative values....