GATE IT 2007 | Question: 31

Question

Consider the C program given below : 

#include <stdio.h>
int main ()    {
    int sum = 0, maxsum = 0,  i,  n = 6;
    int a [] = {2, -2, -1, 3, 4, 2};
    for (i = 0; i < n; i++)    {
            if (i == 0 || a [i]  < 0  || a [i] < a [i - 1])  {
                     if (sum > maxsum) maxsum = sum;
                     sum = (a [i] > 0) ? a [i] : 0;
            }
            else sum += a [i];
    }
    if (sum > maxsum) maxsum = sum ;
    printf ("%d\n", maxsum);

}

What is the value printed out when this program is executed?

• A. $9$
• B. $8$
• C. $7$
• D. $6$

Comments

I think this program is finding the Sum of the Increasing order of the numbers(neglecting negative numbers)  not negative and if any number that breaks the sequence we start summing from that number

---

maximum sum of a contiguous increasing subsequence of positive numbers in the array.

---

https://leetcode.com/problems/maximum-ascending-subarray-sum/description/

Answer 1

Answer is C.

$$\begin{array}{|l|l|l|l|l|} \hline \text{i} &  \text{$A[i]$} & \text{for }\rightarrow\text{ if --- satisfied?}  & \text{maxsum} & \text{sum} \\\hline \text{-} &  \text{-} & \text{-}  & 0 & 0  \\\hline 0 &  \text{$A[0]= 2$} & \text{Yes $(i == 0)$}  & 0 & 2 \\\hline 1 &  \text{$A[1]= -2$} & \text{Yes $(a[i] < 0)$}  & 2 & 0   \\\hline 2 &  \text{$A[2]= -1$} & \text{Yes $(a[i] < 0)$}  & \text{(for $\rightarrow$ if $\rightarrow$ if --- not satisfied)} & 0  \\\hline  3 &  \text{$A[3]= 3$} & \text{No (else executed)}  & \text{(for $\rightarrow$ if $\rightarrow$ if --- not satisfied)} & 3  \\\hline 4 &  \text{$A[4]= 4$} & \text{No (else executed)}  & \text{(for $\rightarrow$ if $\rightarrow$ if --- not satisfied)} & 7 \\\hline  5 &  \text{$A[5]= 2$} & \text{Yes $(a[i] < a[i - 1])$}  & 7 & 2 \\\hline \end{array}$$

[End of for loop]

If (sum (i.e., $2$) $ >$ maxsum (i.e., $7$))   // No

                maxsum $=$ sum;   // Not Executed

printf will output maxsum $= 7$

Comments

“sum = (a [i] > 0) ? a [i] : 0;”

What this statement means?

---

@ gleise_21 read about “ternary operator”

 

---

The algorithm finding the max sum of array of those element which satisfy condition if(a[i]>a[i-1]){ sum=sum+a[i]} where i from 0 to n-1

Answer 2

The algorithm is finding the maximum sum of the monotonically increasing continuous sequence of positive numbers in the array. So, output would be $3+4 = 7.$

Comments

3+4+2 not because its not Monotonically increasing. 3>4 but the series is not increasing after 4 its decreasing, 2 is not greater than 4..

---

The group {2, -2, -1, 3, 4, 2} has 4 elements which are monotonically  increasing.

Those are (-2, -1, 3, 4) because -2 < -1 < 3 < 4. (4 is not less than 2.).

As Arjun sir wrote, the algorithm is for the summation of the positive numbers in the above group. i.e. 3+4 = 7 (not 3+ 4+ 2, as 4 is greater than 2.)

---

@Arjun Sir
How you got to know that this code is of “maximum sum of the monotonically increasing continuous sequence of positive numbers” like how ?? 
Means analyzing that which algo is this will definitely save computation time in exam but coming up with this is not easy , how you knew that this code is of this alog...

Answer 3

first of  all  some  synatax  error  in  above  code segment .  right code given  below

# include <stdio.h>
int main ()    {
    int sum = 0, maxsum = 0,  i,  n = 6;
    int a [] = {2, -2, -1, 3, 4, 2};
    for (i = 0; i < n; i++)    {
            if (i == 0 || a [i]  < 0  || a [i] < a [i - 1])  {
                     if (sum > maxsum) maxsum = sum;
                     sum = (a [i] > 0) ? a [i] : 0;
            }
            else
                sum += a [i];
            }
            if (sum > maxsum) maxsum = sum ;
            printf ("%d\n", maxsum);
}

 

 

 

ans  is  C .

simply  execute  and  trace  value of  sum and  maxsum for i=0 to 5

i  -->      initially  0   1   2   3   4     5

sum            0     0   2   0   3    7    2

maxsum     0     0   2   2   2   2    7

so  maxsum  =  7

Comments

Your answer is correct, but the traced values of sum at i = 0 and i = 1 have been written wrong here. These should be opposite (you may have miss typed).

---

general doubt:

when we are inside the function ,the value of sum is retain back just like static.but once if we out from the for loop the value of sum and mxsum wil be zero?

Answer 4

This is the way we should solve

Answer 5

Caption

Maxsum is 7