Start Learning Free
Skill Test 
Previous Tutorial
18
OctMaximum Subarray Sum Problem
23 Sep 2025
Beginner
495 Views
3 min read
Learn with an interactive course and practical hands-on labs
Free DSA Online Course with Certification
The Maximum Subarray Sum Problem is a classic algorithmic problem where you are given an array of integers (which may include negative numbers) and need to find the contiguous subarray with the largest sum. Return the maximum sum. This problem is efficiently solved using Kadane’s Algorithm.
85% of top tech companies prioritize DSA expertise in hiring. Start your journey with our Free Data Structures and Algorithms Course now!
Example:
- Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
- Output: 6
- Explanation: The subarray [4, -1, 2, 1] has the largest sum = 6.
Logic
Enter an array of numbers (comma-separated) to find the maximum subarray sum.
Program (Python - Kadane’s Algorithm)
The following Python code uses Kadane’s Algorithm to solve the Maximum Subarray Sum Problem efficiently with O(n) time complexity.
def maxSubArray(nums):
max_sum = nums[0]
current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
# Example usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums)) # Output: 6
Output
For the input nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], the output is:
6Explanation:
The subarray [4, -1, 2, 1] has the maximum sum of 6.
Top developers are already moving into Solution Architect roles. If you stay just a “coder,” you’ll be stuck while they lead. Enroll now in our Java Solution Architect Certification and step up.
Take our Datastructures skill challenge to evaluate yourself!
In less than 5 minutes, with our skill challenge, you can identify your knowledge gaps and strengths in a given skill.
600+ Quick notes
900+ Hands-on labs
50+ Real-world projects
45+ Interview books