Master Kadane’s Algorithm: Maximum Subarray (LeetCode 53) Explained

Master Kadane’s algorithm to solve LeetCode 53 (Maximum Subarray) in O(N) time and O(1) space. Includes edge cases, full code in Java, Python, and C++, and intuition.

Follow our YouTube Channels:
Trendy VS Vlogs: https://youtube.com/@trendyvsvlogs?si=Xd3L31p5zPXggomY
WhatsApp Channel: https://whatsapp.com/channel/0029Vb9H4vC545v2HaoKk735


================================================================================
BLOG ARTICLE CONTENT (Markdown / HTML)
================================================================================

# 180-Day DSA Roadmap | Day 7: Maximum Subarray (LeetCode #53)

* **Topic:** Arrays & Strings  
* **Pattern:** Kadane’s Algorithm (Dynamic Subarray Sum Optimization)  
* **Difficulty:** Medium / Tier-1 Core Foundation  
* **LeetCode Problem:** LeetCode #53 - Maximum Subarray  
* **Target Companies:** Amazon, Microsoft, Apple, Google, Meta, Adobe  

---

## 1. Problem Statement

Given an integer array `nums`, find the subarray with the largest sum, and return *its sum*.

A **subarray** is a contiguous non-empty sequence of elements within an array.

### Constraints
* $1 \le \text{nums.length} \le 10^5$
* $-10^4 \le \text{nums}[i] \le 10^4$
* **Follow-up:** If you have figured out the $O(N)$ solution, try coding another solution using the divide and conquer approach, which is more subtle.

### Example Walkthrough
```text
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

Explanation: 
The contiguous subarray [4, -1, 2, 1] has the largest sum = 4 + (-1) + 2 + 1 = 6.

Table of Contents

2. Pattern Recognition: Why Kadane’s Algorithm?

Subarray optimization questions are very common in interviews. Kadane’s algorithm applies whenever:

Contiguous Elements Only: The result must come from uninterrupted adjacent indices (unlike a subsequence).
Presence of Negative Numbers: If all numbers were positive, the entire array would always be the maximum subarray. The presence of negative numbers creates local drops, requiring an optimal restart decision.
The “Carry vs. Reset” Decision: At any index i, you must answer one question:
“Does the accumulated sum from the past help me, or does it drag me down?”
If the accumulated sum drops below zero, carrying it forward only penalizes subsequent numbers. Therefore, resetting is always optimal.

3. Algorithmic Approaches

Approach 1: Brute Force (Suboptimal)

Compute the sum of every possible subarray $(i, j)$ using two nested loops.
Time Complexity: $O(N^2)$
Space Complexity: $O(1)$
Verdict: Fails with Time Limit Exceeded (TLE) when $N = 10^5$.

Approach 2: Divide and Conquer (Theoretical Follow-Up)

Split the array in half. The max subarray lies either entirely in the left half, entirely in the right half, or crosses the midpoint.
Time Complexity: $O(N \log N)$
Space Complexity: $O(\log N)$ (recursion call stack)
Verdict: Valid and good for academic follow-ups, but suboptimal for practical production code.

Approach 3: Kadane’s Algorithm (Optimal MNC Standard)

Maintain two variables:
- current_sum: The running sum of the active subarray ending at index i.
- max_sum: The global maximum sum observed so far.
Initialize both to nums[0]. (⚠️ Do not initialize to 0 because the array can contain strictly negative numbers!).
Iterate through nums starting from index 1:
- current_sum = max(nums[i], current_sum + nums[i])
  (Either start a fresh subarray at nums[i], or append nums[i] to the existing subarray).
- max_sum = max(max_sum, current_sum)

Plaintext

Visual Execution Trace:
nums = [-2,  1, -3,  4, -1,  2,  1, -5,  4]

Index | num | current_sum formula       | current_sum | max_sum
------|-----|---------------------------|-------------|---------
Init  | -2  | -                         | -2          | -2
0     |  1  | max(1, -2 + 1)            |  1 (RESET)  |  1
1     | -3  | max(-3, 1 + (-3))         | -2 (KEEP)   |  1
2     |  4  | max(4, -2 + 4)            |  4 (RESET)  |  4
3     | -1  | max(-1, 4 + (-1))         |  3 (KEEP)   |  4
4     |  2  | max(2, 3 + 2)             |  5 (KEEP)   |  5
5     |  1  | max(1, 5 + 1)             |  6 (KEEP)   |  6  <── GLOBAL MAX
6     | -5  | max(-5, 6 + (-5))         |  1 (KEEP)   |  6
7     |  4  | max(4, 1 + 4)             |  5 (KEEP)   |  6

Final Result: max_sum = 6

4. Production-Ready Code Implementations

Java Solution

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Decide: extend existing subarray or start fresh from nums[i]
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}

Python 3 Solution

Python

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        current_sum = nums[0]
        max_sum = nums[0]

        for i in range(1, len(nums)):
            # If current_sum becomes negative, nums[i] starts a new subarray
            current_sum = max(nums[i], current_sum + nums[i])
            max_sum = max(max_sum, current_sum)

        return max_sum

C++ Solution

C++

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxSubArray(std::vector<int>& nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            currentSum = std::max(nums[i], currentSum + nums[i]);
            maxSum = std::max(maxSum, currentSum);
        }

        return maxSum;
    }
};

5. Complexity Analysis

Time Complexity: $O(N)$
A single pass through the array of length $N$. Each step executes only constant-time comparisons and additions.
Space Complexity: $O(1)$
Memory footprint is strictly constant, using only two integer accumulator variables without additional allocations.

6. Key Takeaways & Common Interview Traps

The All-Negative Array Trap:
If the input is [-5, -2, -8, -1], initializing max_sum = 0 will cause your code to return 0, which is incorrect because the subarray must be non-empty! The correct answer is -1. Always initialize current_sum = nums[0] and max_sum = nums[0].
Printing the Subarray (Popular Interview Variation):
If the interviewer asks to return the actual subarray rather than just the sum, maintain two helper pointers: track start, temp_start, and end whenever max_sum updates.

================================================================================
SEO & METADATA SECTION (Copy to your Website CMS / WordPress)
================================================================================

Master Kadane’s Algorithm: Maximum Subarray (LeetCode 53) Explained | Day 7 of 180

Master Kadane’s algorithm to solve LeetCode 53 (Maximum Subarray) in O(N) time and O(1) space. Includes edge cases, full code in Java, Python, and C++, and intuition.

Maximum Subarray LeetCode 53, Kadanes Algorithm Explained, Max Subarray Sum Java Python Cpp, LeetCode 53 Solution

leetcode 53, maximum subarray, kadanes algorithm, dynamic programming, array algorithms, contiguous subarray, dsa roadmap, dsa interview questions, coding interview preparation, data structures and algorithms, leetcode solutions, kadane pattern, leetcode medium, faang interview preparation, mnc coding questions, amazon coding interview, google coding interview, microsoft interview questions, meta coding interview, adobe coding questions, apple interview questions, leetcode 53 java, leetcode 53 python, leetcode 53 cpp, java dsa, python dsa, cpp dsa, time complexity o n, space complexity o 1, array interview questions, maximum sum subarray, divide and conquer subarray, top dsa patterns, software engineer jobs, campus placement preparation, competitive programming, vs coding academy, 180 days dsa, dsa cheat sheet, cracking the coding interview, tech interview prep, leetcode patterns, software development engineer, sde 1 preparation, single pass algorithm, coding questions for freshers, dsa placement series, engineering placements, leetcode practice, data structures roadmap