CA 11 - Kadanes Algorithm - P2

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

A subarray is a continuous part of the array.

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

Approach

We use Kadane’s Algorithm, which efficiently finds the answer in one pass.

• Keep a running sum of the current subarray
• At each step, decide whether to continue the current subarray or start fresh
• Track the maximum sum seen so far

Steps:

• Initialize current_sum and max_sum with the first element
• Traverse the array:
  • current_sum = max(num, current_sum + num)
  • max_sum = max(max_sum, current_sum)

This way, we always maintain 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))