Kadane's Algorithm Maximum Subarray in DSA C#

Mental Model

Find the largest sum of a continuous part of the list by keeping track of the best sum ending at each position.

Analogy: Imagine walking along a path with ups and downs in height. You want to find the highest hill you can climb without going back, by deciding at each step whether to start fresh or continue climbing.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Index:  0   1   2   3   4   5   6   7   8

max_ending_here and max_so_far start at first element -2

Dry Run Walkthrough

Input: array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Goal: Find the maximum sum of any continuous subarray

Step 1: Start with first element: max_ending_here = max_so_far = -2

max_ending_here = -2, max_so_far = -2

Why: Initialize with first element to start tracking sums

Step 2: Move to element 1: max_ending_here = max(1, -2 + 1) = 1; max_so_far = max(-2, 1) = 1

max_ending_here = 1, max_so_far = 1

Why: Decide to start new subarray at 1 because it is better than continuing

Step 3: Move to element -3: max_ending_here = max(-3, 1 + -3) = -2; max_so_far = max(1, -2) = 1

max_ending_here = -2, max_so_far = 1

Why: Continuing subarray is worse, but max_so_far stays 1

Step 4: Move to element 4: max_ending_here = max(4, -2 + 4) = 4; max_so_far = max(1, 4) = 4

max_ending_here = 4, max_so_far = 4

Why: Start new subarray at 4 because it improves sum

Step 5: Move to element -1: max_ending_here = max(-1, 4 + -1) = 3; max_so_far = max(4, 3) = 4

max_ending_here = 3, max_so_far = 4

Why: Continue subarray, max_so_far unchanged

Step 6: Move to element 2: max_ending_here = max(2, 3 + 2) = 5; max_so_far = max(4, 5) = 5

max_ending_here = 5, max_so_far = 5

Why: Continuing subarray improves sum

Step 7: Move to element 1: max_ending_here = max(1, 5 + 1) = 6; max_so_far = max(5, 6) = 6

max_ending_here = 6, max_so_far = 6

Why: Continuing subarray improves sum further

Step 8: Move to element -5: max_ending_here = max(-5, 6 + -5) = 1; max_so_far = max(6, 1) = 6

max_ending_here = 1, max_so_far = 6

Why: Subarray sum drops but max_so_far stays

Step 9: Move to element 4: max_ending_here = max(4, 1 + 4) = 5; max_so_far = max(6, 5) = 6

max_ending_here = 5, max_so_far = 6

Why: Subarray sum improves but not beyond max_so_far

Result:

max_so_far = 6 (subarray [4, -1, 2, 1])

Annotated Code

DSA C#

using System;

class KadaneAlgorithm
{
    public static int MaxSubArray(int[] nums)
    {
        if (nums == null || nums.Length == 0) return 0;
        int maxEndingHere = nums[0];
        int maxSoFar = nums[0];

        for (int i = 1; i < nums.Length; i++)
        {
            maxEndingHere = Math.Max(nums[i], maxEndingHere + nums[i]); // choose to start new or continue
            maxSoFar = Math.Max(maxSoFar, maxEndingHere); // update max found so far
        }

        return maxSoFar;
    }

    static void Main()
    {
        int[] input = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        int result = MaxSubArray(input);
        Console.WriteLine(result);
    }
}

maxEndingHere = Math.Max(nums[i], maxEndingHere + nums[i]); // choose to start new or continue

decide whether to start a new subarray at current element or continue previous

maxSoFar = Math.Max(maxSoFar, maxEndingHere); // update max found so far

update the maximum subarray sum found so far

Output

6

Complexity Analysis

Time: O(n) because we scan the array once, updating sums at each step

Space: O(1) because we only keep track of two variables regardless of input size

vs Alternative: Compared to checking all subarrays (O(n^2)), Kadane's is much faster by using running sums

Edge Cases

empty array

returns 0 as no subarray exists

DSA C#

if (nums == null || nums.Length == 0) return 0;

array with one element

returns that element as max subarray sum

DSA C#

int maxEndingHere = nums[0];

all negative numbers

returns the largest (least negative) element

DSA C#

maxEndingHere = Math.Max(nums[i], maxEndingHere + nums[i]);

When to Use This Pattern

When you need the largest sum of a continuous part of a list, reach for Kadane's algorithm because it efficiently tracks sums without checking all subarrays.

Common Mistakes

Mistake: Not resetting maxEndingHere when current element alone is better than continuing sum
Fix: Use Math.Max(nums[i], maxEndingHere + nums[i]) to decide whether to start fresh or continue

Summary

Finds the maximum sum of any continuous subarray in a list.

Use when you want the largest sum of consecutive elements efficiently.

The key insight is to track the best sum ending at each position, deciding to start fresh or continue.

Practice

1. What does Kadane's Algorithm primarily help to find in an array of integers?

easy

A. The minimum element in the array

B. The maximum sum of a contiguous subarray

C. The total sum of all elements

D. The number of positive elements

Solution

1. Step 1: Understand the problem Kadane's Algorithm solves

   Kadane's Algorithm is designed to find the maximum sum of any contiguous subarray within a given array.

2. Step 2: Differentiate from other array operations

   It does not find minimum elements, total sums, or count positives, but specifically the largest sum of a continuous segment.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option B

4. Quick Check:

   Maximum subarray sum = The maximum sum of a contiguous subarray [OK]

Hint: Kadane's finds max sum in continuous subarray fast [OK]

Common Mistakes:

• Confusing maximum subarray sum with total array sum
• Thinking it finds minimum or count of elements
• Assuming it works on non-contiguous elements

2. Which of the following is the correct initialization for Kadane's Algorithm variables in C#?

easy

A. int maxSoFar = 0, maxEndingHere = 0;

B. int maxSoFar = int.MaxValue, maxEndingHere = int.MaxValue;

C. int maxSoFar = int.MinValue, maxEndingHere = 0;

D. int maxSoFar = 0, maxEndingHere = int.MinValue;

Solution

1. Step 1: Understand variable roles in Kadane's Algorithm

   maxSoFar stores the maximum sum found so far, so it should start very low (int.MinValue) to handle negative arrays. maxEndingHere tracks current subarray sum and starts at 0.

2. Step 2: Check each initialization

   int maxSoFar = int.MinValue, maxEndingHere = 0; correctly initializes maxSoFar to int.MinValue and maxEndingHere to 0, allowing correct updates during iteration.

3. Final Answer:

   int maxSoFar = int.MinValue, maxEndingHere = 0; -> Option C

4. Quick Check:

   Initialize maxSoFar low, maxEndingHere zero [OK]

Hint: Start maxSoFar at int.MinValue to handle negatives [OK]

Common Mistakes:

• Initializing maxSoFar to 0 causes wrong results with all negatives
• Setting maxEndingHere to int.MinValue breaks sum calculation
• Using int.MaxValue causes logic errors

3. What is the output of the following C# code using Kadane's Algorithm?

int[] arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int maxSoFar = int.MinValue, maxEndingHere = 0;
foreach (int x in arr) {
    maxEndingHere = Math.Max(x, maxEndingHere + x);
    maxSoFar = Math.Max(maxSoFar, maxEndingHere);
}
Console.WriteLine(maxSoFar);

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Trace Kadane's Algorithm on the array

   Iterate and update maxEndingHere and maxSoFar:
   - Start maxSoFar = -∞, maxEndingHere = 0
   - x=-2: maxEndingHere=max(-2,0-2)=-2; maxSoFar=max(-∞,-2)=-2
   - x=1: maxEndingHere=max(1,-2+1)=1; maxSoFar=max(-2,1)=1
   - x=-3: maxEndingHere=max(-3,1-3)=-2; maxSoFar=1
   - x=4: maxEndingHere=max(4,-2+4)=4; maxSoFar=4
   - x=-1: maxEndingHere=max(-1,4-1)=3; maxSoFar=4
   - x=2: maxEndingHere=max(2,3+2)=5; maxSoFar=5
   - x=1: maxEndingHere=max(1,5+1)=6; maxSoFar=6
   - x=-5: maxEndingHere=max(-5,6-5)=1; maxSoFar=6
   - x=4: maxEndingHere=max(4,1+4)=5; maxSoFar=6

2. Step 2: Identify the maximum sum found

   The maximum sum found is 6, which corresponds to the subarray [4, -1, 2, 1].

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Track maxEndingHere and maxSoFar stepwise [OK]

Common Mistakes:

• Adding all positive numbers incorrectly
• Not resetting maxEndingHere properly
• Confusing maxSoFar with last maxEndingHere

4. Identify the bug in this Kadane's Algorithm implementation and select the fix:

int maxSoFar = 0, maxEndingHere = 0;
foreach (int x in arr) {
    maxEndingHere += x;
    if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere;
    if (maxEndingHere < 0) maxEndingHere = 0;
}
return maxSoFar;

medium

A. Add a check to skip negative numbers in the loop

B. Remove resetting maxEndingHere to 0 when negative

C. Change maxEndingHere += x to maxEndingHere = x

D. Initialize maxSoFar to int.MinValue instead of 0

Solution

1. Step 1: Analyze initialization impact

   Initializing maxSoFar to 0 causes wrong results if all numbers are negative, as maxSoFar will never be less than 0.

2. Step 2: Correct initialization to handle negatives

   Setting maxSoFar to int.MinValue allows the algorithm to correctly track maximum sums even if all elements are negative.

3. Final Answer:

   Initialize maxSoFar to int.MinValue instead of 0 -> Option D

4. Quick Check:

   Use int.MinValue for maxSoFar to handle negatives [OK]

Hint: Use int.MinValue for maxSoFar to handle all negatives [OK]

Common Mistakes:

• Leaving maxSoFar at 0 causes wrong max for negative arrays
• Removing reset breaks Kadane's logic
• Changing addition to assignment loses cumulative sum

5. Given an array of integers, how would you modify Kadane's Algorithm to also return the start and end indices of the maximum sum subarray?

hard

A. Track temporary start index when maxEndingHere resets and update final start/end when maxSoFar changes

B. Store all subarrays and pick the max sum one at the end

C. Use two nested loops to find all subarrays and their sums

D. Return the first positive element's index as start and end

Solution

1. Step 1: Understand Kadane's Algorithm extension

   When maxEndingHere resets to current element, record that index as temporary start. When maxSoFar updates, update final start and end indices accordingly.

2. Step 2: Avoid brute force methods

   Storing all subarrays and using two nested loops are brute force and inefficient. Returning the first positive element's index as start and end is incorrect as max subarray may not start at first positive element.

3. Final Answer:

   Track temporary start index when maxEndingHere resets and update final start/end when maxSoFar changes -> Option A

4. Quick Check:

   Track indices on resets and max updates [OK]

Hint: Update start index when resetting maxEndingHere [OK]

Common Mistakes:

• Using nested loops instead of Kadane's linear approach
• Ignoring index tracking during sum updates
• Assuming max subarray always starts at first positive