CA 10 - Kadane's Algorithm

Problem Statement

You are given an integer array arr[]. You need to find the maximum sum of a subarray (containing at least one element) in the array.

Note: A subarray is a continuous part of an array.

Examples:

Input: arr[] = [2, 3, -8, 7, -1, 2, 3]
Output: 11
Explanation: The subarray [7, -1, 2, 3] has the largest sum 11.

Input: arr[] = [-2, -4]
Output: -2
Explanation: The subarray [-2] has the largest sum -2.

Input: arr[] = [5, 4, 1, 7, 8]
Output: 25
Explanation: The subarray [5, 4, 1, 7, 8] has the largest sum 25.

My Goal

For this problem, my goal was to:

Understand how subarrays work
Avoid checking all possible subarrays (which is inefficient)
Learn an optimal approach for maximum sum problems
Improve problem-solving efficiency

Solution

I used Kadane’s Algorithm, which is the most efficient way to solve this problem.

Idea:
Keep a running sum (c)
If the running sum becomes negative, reset it to 0
Keep track of the maximum sum (m) seen so far

This way, we always consider only beneficial subarrays.

Solution Code (Python)

a = [2, 3, -8, 7, -1, 2, 3]

c = 0
m = a[0]

for x in a:
    c += x
    if c > m:
        m = c
    if c < 0:
        c = 0

print(m)

Explanation

c → current running sum
m → maximum sum found so far
Add each element to c
If c exceeds m, update m
If c becomes negative, reset it