Microsoft

  www.microsoft.com
  www.microsoft.com

Interview Question

Software Development Engineer Interview

Maximum continguous subarray of an array,

Answer

Interview Answer

1 Answer

0

Let's assume the array contains both negative and positive values.
We will keep track of the beginning and end of the current sub-array which gives us the greatest sum.

// Find. max contiguous subarray
void subArray(const vector<int>& arr, int& start, int& end, int& sum)
{
    if (arr.empty())
        return;

    sum = 0;
    int currSum(0), i(0), j(0);
    for ( ; i < arr.size() && j < arr.size(); )
    {
        // update currSum if the element is positive
        if (arr[j] >= 0)
            currSum += arr[j++];
        else
        {
            // found a new subarray with greater sum ==> update variables
            if (currSum > sum)
            {
                sum = currSum;
                start = i; end = j-1;
            }

            // reset variables
            currSum = 0;
            i = ++j;
        }
    }

    // edge case - very large number in the last position
    if (currSum > sum)
    {
        sum = currSum;
        start = i; end = j-1;
    }
}

vs on Feb 9, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.