Kadanes Algorithm

Problem Statement

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

Note:
A subarray is a continuous part of an array.

Example 1

Input:

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

Output:

11

Explanation:

The subarray:

[7, -1, 2, 3]

has the largest sum = 11

Example 2

Input:

arr[] = [-2, -4]

Output:

-2

Explanation:

The subarray [-2] has the largest sum.

Even though all elements are negative, we must return the largest among them.

Example 3

Input:

arr[] = [5, 4, 1, 7, 8]

Output:

25

Explanation:

Entire array is the maximum subarray.
Sum = 5 + 4 + 1 + 7 + 8 = 25

Constraints
1 ≤ arr.size() ≤ 10^5
-10^4 ≤ arr[i] ≤ 10^4
Approach – Kadane’s Algorithm

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

Key Idea

At every index, decide:

Should we continue the previous subarray?
Or start a new subarray from the current element?

We keep track of:

current_sum → maximum sum ending at current position
max_sum → overall maximum found so far
Step-by-Step Logic
Initialize:
current_sum = arr[0]
max_sum = arr[0]
Traverse from index 1 to end:

Update current_sum:

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

Update max_sum:

max_sum = max(max_sum, current_sum)
Return max_sum
Time and Space Complexity

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

Only one traversal is required.

Implementation (Python)
class Solution:
def maxSubarraySum(self, arr):
current_sum = arr[0]
max_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

Dry Run Example

For:

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

Step-by-step:

Start → current_sum = 2, max_sum = 2
Add 3 → current_sum = 5, max_sum = 5
Add -8 → current_sum = -3, max_sum = 5
Add 7 → restart → current_sum = 7, max_sum = 7
Add -1 → current_sum = 6, max_sum = 7
Add 2 → current_sum = 8, max_sum = 8
Add 3 → current_sum = 11, max_sum = 11

Final Answer = 11