CA 10 - Kadanes Algorithm

The Problem
Given an array of integers.
The Task is to find the maximum sum of a contiguous subarray.

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

Idea
If your current sum becomes negative:
Drop it immediately
Start fresh from next element

Algorithm Logic
At each index:

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

Example

Array:
[2, 3, -8, 7, -1, 2, 3]
Step-by-step:

• Start with 2 → current = 2
• Add 3 → current = 5
• Add -8 → current = -3 ❌ (bad → drop)
• Start fresh at 7 → current = 7
• Add -1 → current = 6
• Add 2 → current = 8
• Add 3 → current = 11 ✅

answer = 11

Python Code
class Solution:
def maxSubarraySum(self, arr):

    max_sum = arr[0]
    current_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

All numbers are negative:
[-2, -4]
Answer = -2 (not 0)
max_sum = arr[0]