Maximum Subarray Sum – Kadane’s Algorithm

Algorithm Type

• Category: Array Manipulation, In-Place Modification

• Time Complexity: O(n) (linear time)

• Space Complexity: O(1) (constant extra space, ignoring output variable)

• Technique Used: Dynamic Programming, Running Sum

Explanation

Kadane’s Algorithm is used to find the maximum sum of a contiguous subarray in an array of integers (which may contain negative numbers). It efficiently keeps track of the running sum and resets it when necessary to ensure optimal results.

In Kadane’s Algorithm, at each step, we decide whether to:

Start a new subarray (if the previous sum is negative).

• Initialize maxSum to track the maximum sum found so far.

• Initialize currentSum to accumulate subarray sums.

• Iterate through the array:

  • Add the current element to currentSum.

  • If currentSum is greater than maxSum, update maxSum.

  • If currentSum becomes negative, reset it to 0, as negative sums do not contribute positively to future subarrays.

• Return maxSum at the end.

Example With Processing Steps:

Input:

nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}

Output:

Maximum Subarray Sum: 6

public class Solution {
    public int MaxSubArray(int[] nums) {
        // Initialize variables
        int maxSum = nums[0];
        int currentSum = 0;

        foreach (int num in nums) {
            // If currentSum is negative, reset it
            if (currentSum < 0) {
                currentSum = 0;
            }
            // Add the current element to currentSum
            currentSum += num;
            // Update maxSum if needed
            maxSum = Math.Max(maxSum, currentSum);
        }
        return maxSum;
    }
}

Extend the previous subarray (if its sum is positive).

• Initialize maxEnding and res

  • maxEnding: Keeps track of the maximum sum subarray ending at index i.

  • res: Stores the overall maximum subarray sum found so far.

• Iterate through the Array

  • For each element array[i], we decide:

    • Extend the previous subarray (maxEnding + array[i]) if it contributes positively.

    • Start a new subarray (array[i]) if extending the previous subarray results in a smaller sum.

• Update res

  • If the new maxEnding is greater than res, update res.

public class Solution {
  public static int MaxSubArray(int[] array) {
    // Initialize variables
    int maxEnding = array[0];  // Maximum sum subarray ending at current index
    int res = array[0];        // Stores the overall maximum sum

    for(int i = 1; i < array.Length; i++)
    {
        // Find the maximum sum ending at index i by either extending 
        // the maximum sum subarray ending at index i - 1 or by
        // starting a new subarray from index i
        maxEnding = Math.Max(maxEnding + array[i], array[i]);  
          
        // Update res if the maximum subarray sum ending at index i is greater than res
        res = Math.Max(res, maxEnding);
    }
      
    return res;
  }
}

Comparison with Other Maximum Subarray Sum Algorithms

When to Use Kadane’s Algorithm?

✔️ When an optimal O(n) solution is required
✔️ When finding the largest sum of a contiguous subarray
✔️ When modifying the input is not allowed

❌ Not suitable if the problem requires non-contiguous subarrays
❌ Doesn’t track the subarray elements directly (modifications needed for that)

This approach is commonly used in LeetCode problems like:

• "Maximum Subarray" (LeetCode 53)

• "Maximum Sum Circular Subarray" (LeetCode 918, with modifications)