Kadane's Algorithm - II

Introduction

Finding the maximum sum of a contiguous subarray is a classic problem in Data Structures and Algorithms.
It is widely used in real-world applications like financial analysis, signal processing, and more.

This problem is efficiently solved using Kadane’s Algorithm, which works in linear time.

Problem Statement

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

Note: A subarray is a continuous part of the array and 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] has the maximum sum = 11

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

Explanation:
Subarray [-2] gives the maximum sum.

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

Intuition

• If the running sum becomes negative, it will reduce the total
• So we discard it and start a new subarray

Approach (Kadane’s Algorithm)

We maintain two variables:

• current_sum → current subarray sum
• max_sum → maximum sum found so far

Algorithm

• Initialize:

  • current_sum = arr[0]
  • max_sum = arr[0]

• Traverse the array:

  • Update current sum:

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

  • Update max sum:

   max_sum = max(max_sum, current_sum)
  

• 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 Explanation

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

• Start → current = 2, max = 2
• Add 3 → current = 5, max = 5
• Add -8 → current = -3
• Reset → 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 a powerful and efficient method to solve the maximum subarray problem.