Finding Maximum Subarray Sum Using Kadane’s Algorithm in Python

Problem Explanation

You are given an integer array arr[].
Your task is to find the maximum sum of a contiguous subarray (subarray must contain at least one element).

A subarray is a continuous part of the array.

Example:

• Input: arr = [2, 3, -8, 7, -1, 2, 3]
  Output: 11
  Explanation: Subarray [7, -1, 2, 3] has the maximum sum.

• Input: arr = [-2, -4]
  Output: -2

---

Method Used: Kadane’s Algorithm

Kadane’s Algorithm helps us find the maximum subarray sum in a single pass.

Idea:

• Keep adding elements to a running sum
• If the sum becomes negative, reset it
• Track the maximum sum seen so far

---

Why This Method?

• Time complexity: O(n)
• Space complexity: O(1)
• Very efficient compared to brute force (O(n²))
• Widely used in real-world problems

---

Python Code with Explanation

class Solution:
    def maxSubarraySum(self, arr):

Defines the function to find the maximum subarray sum.

---

        max_sum = arr[0]

Initialize max_sum with the first element.
This handles cases where all elements are negative.

---

        current_sum = 0

This variable keeps track of the current running sum.

---

        for num in arr:

Loop through each element in the array.

---

            current_sum += num

Add the current element to the running sum.

---

            if current_sum > max_sum:
                max_sum = current_sum

Update max_sum if the current sum is greater.

---

            if current_sum < 0:
                current_sum = 0

If the running sum becomes negative, reset it to 0.
Because a negative sum will reduce future subarray sums.

---

        return max_sum

Return the maximum subarray sum.

---

Complete Code

class Solution:
    def maxSubarraySum(self, arr):
        max_sum = arr[0]
        current_sum = 0

        for num in arr:
            current_sum += num

            if current_sum > max_sum:
                max_sum = current_sum

            if current_sum < 0:
                current_sum = 0

        return max_sum

---

Step-by-Step Example

Input:

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

Process:

• Start with sum = 0
• Add elements one by one
• Reset when sum becomes negative
• Track maximum

Final Output:

11

---

Time and Space Complexity

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

---

Key Takeaway

Kadane’s Algorithm efficiently finds the maximum subarray sum by avoiding unnecessary calculations and working in a single traversal.

---