CA 10 - Kadanes Algorithm

Problem
Kadane's Algorith
You are given an integer array arr[].
Your task is to find the maximum sum of a contiguous subarray.

A subarray is simply a continuous part of the array.

Examples

• Input: [2, 3, -8, 7, -1, 2, 3] → Output: 11
• Input: [-2, -4] → Output: -2
• Input: [5, 4, 1, 7, 8] → Output: 25

Approach
This problem can be efficiently solved using Kadane’s Algorithm.

Instead of checking all subarrays, we build the solution as we traverse the array.

At each element, decide:

• Extend the current subarray
• Or start a new subarray from the current element

Steps:

• Initialize current_sum and max_sum with the first element

• Traverse the array:

• Update current_sum = max(num, current_sum + num)

• Update max_sum = max(max_sum, current_sum)

This ensures we always keep track of the best possible subarray sum.

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

def maxSubArray(arr):
    current_sum = arr[0]
    max_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)

    return max_sum
arr = [2, 3, -8, 7, -1, 2, 3]
print(maxSubArray(arr))