Find max sum of elements in array [duplicate]

Question

Write a program which by given array of integer values (containing negative integers) finds the maximum sum of successive elements in the array.

Example:

2, 3, -6, -1, 2, -1, 6, 4, -8, 8

Gives

11

I am searching for a solution which is faster than O(N^2).

Answer 1

I think Kadane's Algorithm is what you want

Answer 2

This is actually a textbook problem I studied in college(Data Structures and Algorithms in C by Mark Allen Weiss)...It is a very beautiful and elegant solution and solves in O(N)

int MaxSubsequenceSum(int A[])
{
    int sum = 0, maxSum = 0;

    for (int j = 0; j < A.Length; j++)
    {
        sum = sum + A[j];

        if (sum > maxSum)
            maxSum = sum ;
        else if (sum < 0)
            sum = 0;
    }
    return maxSum;
}