Maximum Sum Of Consecutive Numbers - O(n) solution in C#

Problem:

n numbers (both +ve and -ve) are arranged in a circle. find the maximum sum of consecutive nos. Do this in O(n) time

E.g.: {8,-8,9,-9,10,-11,12}
max = 22 (12 + 8 - 8 + 9 - 9 + 10)

Explanation and algorithm:

We will discuss the problem in two steps. One where we will get the answer in O(n^2). Then we will make it efficient to bring it to O(n).

Step 1:

Let us understand given problem is not straight away Kadane algorithm. Since we need to consider all the rotations of the given array as well. If the array is linear then applying kadane algorithm would give us the largest sum of consecutive numbers.  Hence first approach is to apply Kadane algorithm for all 'n' different arrays, each array starting at 'i'th index and includes all the elements till [i%n + n - 1] elements.

e.g. if 2,3,4, 5 is the given array, {4,5,2,3} is also a possible array like other two. Hence there would be four different arrays in this case. Finding out the maximum of largest consecutive sums of each individual array.

I'm also handling two other cases where all are negative numbers and all are positive numbers.

An array starting at 'i'th location will end at 'i'+ n -1 th location. Use modulus to take care of index.

       public static void PrintHighestSum()
        {
            int[] input = {53, -8, 11 , - 9 , -11, 0, 8};
            int maxEndingHere = 0; 
            int maxTillHere = 0;
            bool isAllPositive = true;
            int sum = 0;
            for(int i=0;i< input.Length;i++)
            {
                isAllPositive = isAllPositive && (input[i] >= 0);                
                if (!isAllPositive) break;
                sum = sum + input[i];
            }
            if (isAllPositive)
            {
                Console.WriteLine(sum);
                return;
            }
            bool isAllNegative = true;


            sum = input[0];
            for (int i = 0; i < input.Length; i++)
            {
                isAllNegative = isAllNegative && (input[i] < 0);                
                if (!isAllNegative) break;
                sum = Math.Max(sum, input[i]);
            }
            if (isAllNegative)
            {
                Console.WriteLine(sum);
                return;
            }


            //Kadane's algorithm
            //maxEndingHere = Math.Max(input[i % input.Length], input[i % input.Length] + maxEndingHere);
            //maxTillHere = Math.Max(maxTillHere, maxEndingHere);
            //here there can be n arrays, since all numbers are arranged in circle
            //each rotation of the number is a different array.. 
            //find max in each array using kadane algo, stack it and then find max
            //n^s solution 


            Stack<int> maxs = new Stack<int>();
            
            for (int i = 0; i < input.Length; i++)
            {
                maxEndingHere = maxTillHere = 0;
                for (int j = i; j < input.Length + i; j++)
                {
                    maxEndingHere = Math.Max(input[j % input.Length], input[j % input.Length] + maxEndingHere);
                    maxTillHere = Math.Max(maxTillHere, maxEndingHere);
                }
                maxs.Push(maxTillHere);
            }
           
            int tempMax = 0;
            maxTillHere = 0;
            for (int i = 0; i < maxs.Count; i++)
            {
                tempMax = maxs.Pop();
                if (tempMax > maxTillHere)
                    maxTillHere = tempMax;
            }
            Console.WriteLine(maxTillHere);
        }




Step 2: (Making the solution efficient) - Linear O(n) solution
This solution is quite tricky not straight forward approach. Once we apply Kadane algorithm for given array we get maximum consecutive sum. When there are negative elements in the array, we can also find out negative consecutive sum. Maximum of (max consecutive sum, sum of all elements - maximum negative consecutive sum) will the expected output. 


To illustrate we will take example of given array itself,  
{8,-8,9,-9,10,-11,12}


Here Max consecutive sum from (0, n-1) we get is  12
Max negative sum is (-11) 
Sum of all elements is  11.


Required Maximum Consecutive Sum  = Max (max cons sum, (sum of all elements - max negative cons sum))
=> Max(12, (11-(-11)) => Max(11, 22) = 22


Below code computes largest consecutive sum of the array from 0,n-1 and also negative consecutive sum(uses easy manipulation using -1 as sign i.e. multiplying max sum with -1 and then comparing max consecutive sum till now). We will call it twice once with 1 to find out consecutive sum and once with -1 to find max negative consecutive sum.


=================================================================================

static int MaximumConsecutiveSum(int[] input, int sign)

{

            int max_so_far = 0, max_ending_here = 0, i;

            for (i = 0; i < input.Length; i++)

            {

                max_ending_here = max_ending_here + input[i];

                if (sign * max_ending_here < 0)

                    max_ending_here = 0;

                if (sign * max_so_far < sign * max_ending_here)

                    max_so_far = max_ending_here;

            }

            return max_so_far;

}

 public static void PrintHighestSum()
 {



            int[] input = { -2, -1, 9, -9, 10,  12 };
            int maxEndingHere = 0; 
            int maxTillHere = 0;
            bool isAllPositive = true;
            int sum = 0;
            for(int i=0;i< input.Length;i++)
            {
                isAllPositive = isAllPositive && (input[i] >= 0);                
                if (!isAllPositive) break;
                sum = sum + input[i];
            }
            if (isAllPositive)
            {
                Console.WriteLine(sum);
                return;
            }
            bool isAllNegative = true;


            sum = input[0];
            for (int i = 0; i < input.Length; i++)
            {
                isAllNegative = isAllNegative && (input[i] < 0);                
                if (!isAllNegative) break;
                sum = Math.Max(sum, input[i]);
            }
            if (isAllNegative)
            {
                Console.WriteLine(sum);
                return;
            }


            sum = 0;
            for (int i = 0; i < input.Length; i++) sum += input[i];
                
            int max = MaximumConsecutiveSum(input, 1);
            int negativeMax = MaximumConsecutiveSum(input, -1);


            max = Math.Max(max, (sum - negativeMax));
            Console.WriteLine(max);
}


=================================================================================
Reference: GeeksforGeeks.org