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

  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.
in Algorithms by Veteran (106k points)
edited by | 3.6k views
Time Complexity is O(n^3) ...right?
Yes bro

4 Answers

+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++)  
//checks whether sum of elements of each subarray is greater
//than the current max, if so, then assign it to currentmax
                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 by

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

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

and what does *E mean?

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


Can you give an example, where below part will be true ?
   Y = z;

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

@Monanshi When there are negative numbers.
@Arjun Thanks sir.


// 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

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

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. 

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.
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 by
0 votes
sum of subarray can never be greater than sum of all elements of an array .therefore ans is D
by (331 points)
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...
-5 8 -7 6 9

sum of each element of array is 11 
sub array last two element's sum is 15  .
clear ??????

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
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 here the array may or maynot contain negative values....
0 votes
Option a
by (139 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,832 questions
57,686 answers
107,204 users