Data Structures for Coding Interviews in C#/

...

/

Solution Review: Maximum Sum Subarray

Solution Review: Maximum Sum Subarray

This review discusses the solution to the "Maximum Sum Subarray" challenge in detail.

We'll cover the following...

Solution (Kadane’s algorithm)

This algorithm takes a dynamic programming approach to solving the maximum subarray sum problem. Take a look at the algorithm.

Press + to interact
using System;
namespace chapter_2
{
    class Solution
    {
        //Maximum Sum Subarray
        static int maxSumArr(int []arr, int arrSize)
        {
            if (arrSize < 1)
            {
                return 0;
            }
            int currMax = arr[0];
            int globalMax = arr[0];
            for (int i = 1; i < arrSize; i++)
            {
                if (currMax < 0)
                {
                    currMax = arr[i];
                }
                else
                {
                    currMax += arr[i];
                }
                if (globalMax < currMax)
                {
                    globalMax = currMax;
                }
            }
            return globalMax;
        }
        static void Main(string[] args)
        {
            int []arr = { -4, 2, -5, 1, 2, 3, 6, -5, 1 };
            int arrSize = arr.Length;
            int maxSum = maxSumArr(arr, arrSize);
            Console.WriteLine("Maximum contiguous sum is " + maxSum);
            return;
        }
    }
}

The basic idea of “Kadane’s algorithm” is to scan the entire array. At each position, find the maximum sum of the subarray ending there. This is achieved by keeping a currMax for the current array index and a globalMax. The algorithm is as follows:

 ...