Wednesday, November 17, 2010

MicroSoft Question: Given a sequence, find the subsequence with maximum sum.

int main()
{
    int arr[] = { 1, 3, -5, 7, 2 ,-4, 9, -3};
    int length = sizeof(arr) / sizeof(*arr);
    int tempSum = 0, maxSum = 0, tempStartIndex = 0, startIndex = 0, endIndex = 0;
  
    for(int i=0; i<length; ++i)
    {
        tempSum += arr[i];
        if(tempSum < 0)
        {
            tempStartIndex = i+1;
            tempSum = 0;
            continue;
        }

        if(tempSum > maxSum)
        {
            maxSum = tempSum;
            startIndex = tempStartIndex;
            endIndex = i;
        }

    }
    cout<<"Maximum Sum = "<<maxSum<<" Between indices "<<startIndex<<" "<<
   endIndex<<'\n';
    return 0;
}

4 comments:

  1. your prog not work for
    3,5 ,8,8,-1,8,6

    ReplyDelete
  2. It is working and the answer is whole array --

    Output of Program--

    Maximum Sum = 37 Between interval 0 6

    ReplyDelete
  3. Not working for array with all -ve numbers.

    Two changes required,
    1. Initialize maxsum = a[0]
    2. change the order of 'if' inside the for loop.

    for(int i=0; i maxSum)
    {
    maxSum = tempSum;
    startIndex = tempStartIndex;
    endIndex = i;
    }
    if(tempSum < 0)
    {
    tempStartIndex = i+1;
    tempSum = 0;
    continue;
    }
    }

    ReplyDelete
  4. Yes, It will not work in that case... I think in the exercise, I have cover that case. Let me know if I did some blunder in that also :)

    http://algods-cracker.blogspot.com/2011/10/find-maximum-sum-of-sub-array-within.html

    ReplyDelete