Problem Statement
Given an integer array arr[], find the maximum sum of a contiguous subarray.
Note:
A subarray is a continuous part of the array.
Examples
Input: arr = [2, 3, -8, 7, -1, 2, 3]
Output: 11
Input: arr = [-2, -4]
Output: -2
Input: arr = [5, 4, 1, 7, 8]
Output: 25
Objective
• Find the maximum possible sum from a subarray
• Subarray must be continuous
• Must contain at least one element
Approach: Kadane’s Algorithm
🧠 Idea
• Traverse the array once
• Keep track of:
o current_sum → sum of current subarray
o max_sum → maximum sum found so far
Logic
At each element:
• Add it to current_sum
• If current_sum becomes greater than max_sum → update max_sum
• If current_sum becomes negative → reset it to current element
Python Code
arr = [2, 3, -8, 7, -1, 2, 3]
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)
print(max_sum)
________________________________________Step-by-Step
For:
[2, 3, -8, 7, -1, 2, 3]
Element Current Sum Max Sum
2 2 2
3 5 5
-8 -3 5
7 7 7
-1 6 7
2 8 8
3 11 11
Final Output:
11
Complexity
• Time: O(n) (single pass)
• Space: O(1)
Edge Cases
• All negative numbers → return largest (least negative)
• Single element array
• Large input size
Why Kadane’s Algorithm?
• Most efficient solution
• Avoids checking all subarrays (which is O(n²))
• Widely asked in interviews
Final Thoughts
Kadane’s Algorithm is a powerful technique for solving problems involving:
• Maximum subarrays
• Continuous sequences
• Optimization problems
Top comments (0)