53.Maximum Subarray

📘 LeetCode 53: Maximum Subarray

📌 Problem Overview

• Problem Number: 53
• Problem Name: Maximum Subarray
• Difficulty: Medium
• Category: 1D Dynamic Programming
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the 1D Dynamic Programming algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/53.Maximum-Subarray/:

Console.WriteLine(MaxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
Console.WriteLine(MaxSubArray([1])); // 1
Console.WriteLine(MaxSubArray([5, 4, -1, 7, 8])); // 23
 
int MaxSubArray(int[] nums)
{
    int currentSum = nums[0];
    int maxSum = nums[0];
    for (var i = 1; i < nums.Length; i++)
    {
        currentSum = Math.Max(currentSum + nums[i], nums[i]);
        maxSum = Math.Max(currentSum, maxSum);
        Console.WriteLine($"currentSum: {currentSum}, maxSum: {maxSum}");
    }
    return currentSum;
}
 
int MaxSubArrayMissCaseMinusNumber(int[] nums)
{
    int currentSum = nums[0];
    int maxSum = int.MinValue;
    for (var i = 0; i < nums.Length; i++)
    {
        currentSum += nums[i];
        maxSum = currentSum;
        if (currentSum > maxSum)
        {
            maxSum = currentSum;
        }
        Console.WriteLine($"currentSum: {currentSum}, maxSum: {maxSum}");
        if (currentSum < 0)
        {
            currentSum = 0;
        }
    }
    return maxSum;
}

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.