Kadane's Algorithm

Introduction

In many real-world scenarios, we need to find a continuous segment of data that gives the best result.

This problem asks us to find the maximum sum of a contiguous subarray, which is a classic problem solved using Kadane’s Algorithm.

Problem Statement

Given an integer array arr[],
find the maximum sum of a subarray (contiguous elements).

Note: A subarray must contain at least one element.

Examples

Example 1:
Input: [2, 3, -8, 7, -1, 2, 3]
Output: 11

Explanation:
Subarray [7, -1, 2, 3] gives maximum sum = 11

Example 2:
Input: [-2, -4]
Output: -2

Explanation:
Best subarray is [-2]

Example 3:
Input: [5, 4, 1, 7, 8]
Output: 25

Intuition

• If the current sum becomes negative, it will reduce future results
• So we discard it and start fresh

Approach (Kadane’s Algorithm)

We maintain two variables:

• current_sum → sum of current subarray
• max_sum → best sum found so far

Algorithm Steps

1. Initialize:

• current_sum = arr[0]

• max_sum = arr[0]

  1. Traverse the array:

• current_sum = max(arr[i], current_sum + arr[i])

• max_sum = max(max_sum, current_sum)

  1. Return max_sum

Code (Python)

def max_subarray_sum(arr):
    current_sum = arr[0]
    max_sum = arr[0]

    for i in range(1, len(arr)):
        current_sum = max(arr[i], current_sum + arr[i])
        max_sum = max(max_sum, current_sum)

    return max_sum

Step-by-Step Idea

For [2, 3, -8, 7, -1, 2, 3]:

• Start → current = 2, max = 2
• Add 3 → current = 5, max = 5
• Add -8 → current = -3 (reset next step)
• Take 7 → current = 7, max = 7
• Add -1 → current = 6
• Add 2 → current = 8
• Add 3 → current = 11 → max = 11

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Conclusion

Kadane’s Algorithm is one of the most efficient and elegant solutions for finding the maximum subarray sum.
It is widely used in interviews and helps build strong problem-solving skills.