CA 11 - Kadanes Algorithm - P2

Problem Statement

Given an integer array, find the maximum sum of a contiguous subarray.

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

Subarray: [7, -1, 2, 3]

Kadane’s Algorithm (Core Idea)
At every element, ask:
Should I continue the current subarray or start a new one?

Idea:
If your current sum becomes negative:
Drop it immediately

Step-by-Step Logic
We maintain two variables:

• current_sum → sum of current subarray
• max_sum → best result so far Formula: current_sum = max(arr[i], current_sum + arr[i]) max_sum = max(max_sum, current_sum)

Python Implementation
python
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

If all elements are negative:
Input: [-2, -4]
Output: -2