Geek asks and answers

Find the maximum amount of elements in an array

Write a program that, given an array of integer values ​​(containing negative integers), finds the maximum sum of consecutive elements in the array.

Example:

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

gives

eleven

I am looking for a solution that is faster than O (N ^ 2).

+5
source share
3 answers

I think the Kadan algorithm is what you want

+9
source

This is actually a problem with a textbook that I studied in college (Data Structures and Algorithms in C by Mark Allen Weiss) ... This 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;
}
+4
source

, : sum=arr[0]+arr[1]+arr[2] sum=0 . ​​

-1
source

More articles:


All Articles