Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C#

Solution Review: Maximum Sum Subarray

Explore Kadane's algorithm to solve the maximum sum subarray problem using a dynamic programming approach. Understand how to track current and global maximum sums for arrays and learn its efficient O(n) time and O(1) space complexity implementation.

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.

C#
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:

 ...