Kadane’s Algorithm is one of the most famous and frequently asked algorithms in coding interviews.

It is used to find the maximum sum of a contiguous subarray in an array.

What makes Kadane’s Algorithm special is that it solves a problem that looks quadratic at first glance in linear time.

If you understand this algorithm properly, you also build a strong foundation for

➜ dynamic programming

➜ prefix sum intuition

➜ optimization thinking

Who Should Learn Kadane’s Algorithm

This topic is ideal if you already understand

➜ array traversal

➜ prefix sum basics

➜ sliding window technique

Kadane’s Algorithm often acts as a bridge between basic array problems and dynamic programming.

The Problem Kadane’s Algorithm Solves

Given an integer array, you need to find the maximum sum of any continuous subarray.

Example

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6

The subarray [4, -1, 2, 1] gives the maximum sum.

Why Brute Force Fails

In a brute-force approach, you would

➜ generate all possible subarrays

➜ calculate their sums

➜ return the maximum

This approach takes O(n²) time and fails for large inputs.

Kadane’s Algorithm removes unnecessary work by making a smart observation.

The Core Idea Behind Kadane’s Algorithm

While traversing the array, you keep track of two things

➜ the maximum subarray sum ending at the current index

➜ the overall maximum subarray sum found so far

If the current running sum becomes negative, it is better to reset it and start fresh from the next element.

This simple idea makes the algorithm extremely powerful.

Real-Life Analogy

Imagine tracking your daily profit and loss.

If losses keep adding up and your total becomes negative, you stop counting from that day and restart from the next profitable day.

Kadane’s Algorithm works the same way by dropping harmful subarrays.

Step-by-Step Dry Run

Given the array

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Initialize

currentSum = 0
maxSum = -Infinity

Traversal

-2 → currentSum = -2 → maxSum = -2 → reset currentSum to 0
 1 → currentSum = 1  → maxSum = 1
-3 → currentSum = -2 → maxSum = 1 → reset currentSum to 0
 4 → currentSum = 4  → maxSum = 4
-1 → currentSum = 3  → maxSum = 4
 2 → currentSum = 5  → maxSum = 5
 1 → currentSum = 6  → maxSum = 6
-5 → currentSum = 1  → maxSum = 6
 4 → currentSum = 5  → maxSum = 6

Final answer

6

JavaScript Implementation

function kadane(nums) {
  let currentSum = 0;
  let maxSum = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    currentSum += nums[i];
    maxSum = Math.max(maxSum, currentSum);
    if (currentSum < 0) {
      currentSum = 0;
    }
  }
  return maxSum;
}

This solution is clean, readable, and interview-ready.

Time and Space Complexity

Kadane’s Algorithm runs in linear time.

Each element is visited exactly once.

No extra data structures are used.

This gives

➜ Time complexity: O(n)
➜ Space complexity: O(1)

Edge Case: All Numbers Are Negative

If the array contains only negative numbers, the algorithm still works because maxSum starts from -Infinity.

Example

[-5, -2, -3]

Output

-2

The algorithm correctly returns the largest element.

Kadane’s Algorithm vs Sliding Window

Sliding window works best when the window size is fixed or condition-based.

Kadane’s Algorithm works best when

➜ the goal is maximum subarray sum

➜ window size is not fixed

➜ negative numbers influence decisions

Kadane’s Algorithm can be seen as a dynamic sliding window with reset logic.

Common Interview Questions on Kadane’s Algorithm

How does Kadane’s Algorithm handle negative numbers

Why do we reset the running sum when it becomes negative

Can Kadane’s Algorithm be used for minimum subarray sum

How would you modify it to return the subarray itself

Interviewers often test understanding, not just the code.

What to Read Next

DSA Complete RoadMap 2026 -

https://www.dsawithpiyush.com/post/data-structures-and-algorithm-complete-roadmap-2026

Array Traversal – Beginner to Interview Level

https://www.dsawithpiyush.com/post/array-traversal-in-data-structure-or-ds

Prefix Sum Explained With Real Examples -

https://www.dsawithpiyush.com/post/prefix-sum-explained-with-real-examples-dsa


Final Advice from DSA With Piyush

Kadane’s Algorithm teaches a powerful lesson.

If something hurts your total, let it go and start fresh.

Once this mindset clicks, many optimization problems become simple.