Given a sequence of n real numbers A(1) … A(n), program to find a contiguous subarray with the largest sum

For example,

var arr = new int[] {-2, 1,-3, 4,-1, 2, 1,-5, 4 };

the contiguous sub array with the largest sum is [4, −1, 2, 1], with sum 6.

Solution

Solution via iterating over all array elements repeatedly, try each key elements

using System;
namespace MaximumSubarray
{
    class Program
    {
        static void Main()
        {
            Console.WriteLine("Enter array size:");
            var n = Convert.ToInt32(Console.ReadLine());
            var arr = new int[n]; //{ -2, 1, -3, 4, -1, 2, 1, -5, 4 };
            Console.WriteLine("Enter array elements:");
            for (var i = 0; i < n; i++)
            {
                arr[i] = Convert.ToInt32(Console.ReadLine());
            }
            Console.WriteLine($"Max sum of array is {MaxSum(arr)}");
        }
        static int MaxSum(int[] a)
        {
            var maxSum = 0;
            for (var i = 0; i < a.Length; i++)
            {
                var newSum = 0;
                for (var j = i; j < a.Length; j++)
                {
                    newSum += a[j];
            if (newSum > maxSum)
            {
                maxSum = newSum;
            }
        }
    }
        return maxSum;
        }
    }
    
}

Execute above program to see the output

Using Kadane’s algorithm – Dynamic Programming

Kadane’s algorithm scans the given array A[1…n] from left to right. In the jth step, it computes the subarray with the largest sum ending at j; this sum is maintained in variable current_sum]. Moreover, it computes the subarray with the largest sum anywhere in A[1…j] maintained in variable best_sum and easily obtained as the maximum of all values of current_sum seen so far, cf. line 7 of the algorithm.

Pseudocode:

def max_subarray(numbers):    
"""Find the largest sum of any contiguous subarray."""     
best_sum = 0  
# or: float('-inf')     
current_sum = 0     
for x in numbers:         
current_sum = max(0, current_sum + x)         
best_sum = max(best_sum, current_sum)    
return best_sum

Here is the C# solution of the problem using Kadane’s algorithm

using System;
namespace MaximumSubarray
{
    class DynamicProgramming
    {
        static void Main()
        {
            Console.WriteLine("Enter array size:");
            var n = Convert.ToInt32(Console.ReadLine());
            var arr = new int[n]; //{ -2, 1, -3, 4, -1, 2, 1, -5, 4 };
            Console.WriteLine("Enter array elements:");
            for (var i = 0; i < n; i++)
            {
                arr[i] = Convert.ToInt32(Console.ReadLine());
            }
                Console.WriteLine($"Max sum of array is {MaxSum(arr)}");
        }
        
        static int MaxSum(int[] a)
        {
            var maxSum = 0;
            var newSum = 0;
            foreach (var t in a)
            {
                newSum = Math.Max(t, newSum + t);
                maxSum = Math.Max(maxSum, newSum);
            }
        return maxSum;
        }
    }   
}

Execute above program to see the output