⬅ Previous Topic
Find Majority Element in Array (more than n/3 times)Next Topic ⮕
Print Subarray with Maximum Sum⬅ Previous Topic
Find Majority Element in Array (more than n/3 times)Next Topic ⮕
Print Subarray with Maximum SumTopic Contents
Given an array of integers (which may include negative numbers), your task is to find the maximum sum of any contiguous subarray.
This problem is also known as the Maximum Subarray Problem.
0
.Use Kadane's Algorithm to solve it efficiently in linear time.
arr
.max_sum
and current_sum
with the value of the first element.current_sum
as the maximum of the current element or current_sum + current_element
.max_sum
if current_sum
is greater than max_sum
.max_sum
as the result.def max_subarray_sum(arr):
max_sum = current_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
# Sample Input
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum:", max_subarray_sum(arr))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n) | Even in the best case, Kadane's Algorithm must iterate through all elements of the array to compute the maximum subarray sum. |
Average Case | O(n) | Kadane's Algorithm processes each element once, maintaining a running sum and updating the maximum found so far in linear time. |
Worst Case | O(n) | In all cases—whether the array has all negative values, all positives, or a mix—Kadane's algorithm completes in linear time by scanning the entire array. |
O(1)
Explanation: Kadane's Algorithm uses only constant space with a few variables (max_sum
and current_sum
) to track the state—no extra arrays or recursion are used.
⬅ Previous Topic
Find Majority Element in Array (more than n/3 times)Next Topic ⮕
Print Subarray with Maximum SumYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.