Search⌘ K
AI Features
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:

currMax = A[0]
globalMax = A[0]
for i = 1 -> size of A
    if currMax is less than 0
        then currMax = A[i]
    otherwise 
        currMax = currMax + A[i]
    if globalMax is less than currMax 
        then globalMax = currMax

The solution above only finds the maximum contiguous sum in the array; however, it can easily be modified to track the starting and ending indexes of this subarray.

Time complexity

The runtime complexity of this solution is linear: O(n)O(n). The space complexity of this solution is constant: O(1)O(1).

Run through an example to understand how it works. Initially, the currMax and globalMax are both set to the value at A[0]; that is, -4: