The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
2.1k 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.
asked in Algorithms by Veteran (99.8k points)
edited by | 2.1k views

4 Answers

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

 

answered by Active (3.3k points)
edited by
0

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?

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...??
0
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... ?
+1

@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?

+15
@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. 

+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.
answered by Loyal (8.3k points)
edited by
0 votes
Option a
answered by (19 points)
–2 votes
sum of subarray can never be greater than sum of all elements of an array .therefore ans is D
answered by (319 points)
+19
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...
+9
-5 8 -7 6 9

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



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

38,052 questions
45,543 answers
131,851 comments
48,879 users