CMI-2021-DataScience-A: 3

Question

Consider the following code, in which $\text{A}$ is an array indexed from $0.$

function foo (A , n) {
    m = A [0] ;
    x = 0 ;
    for i = 0 to n – 1  {
        x = x + A [i] ;
        if (m < x)  {
            m = x ;
        }
        if (x < 0)  {
            x = 0 ;
        }

    }
    return (m) ;
}

If $\text{A}=[-12, -3, 5, 10, 8, -16, -23, 12, -5, 7]$, what will $\textsf{foo(A, 10)}$ return?

• A. $23$
• B. $17$
• C. $-17$
• D. $35$

Answer 1

Answer: A

This is very famous Kadane’s Algorithm that is used to find the maximum sum of contiguous subarray.

Idea of this algorithm is first initialize the max sum as the initial element and current sum to 0. Now iterate through the array and update the current sum. If current sum is greater than the max sum then update the max sum to the current sum. If our current sum gets below 0 then just update the current sum to 0 and move ahead.

To know more about this algorithm refer : https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

For A = [-12, -3, 5, 10, 8, -16, -23, 12, -5, 7], largest subarray sum would be 23 for subarray [5, 10, 8].