⬅ Previous Topic
Maximum Subarray Sum using Kadane's AlgorithmNext Topic ⮕
Stock Buy and Sell⬅ Previous Topic
Maximum Subarray Sum using Kadane's AlgorithmNext Topic ⮕
Stock Buy and SellTopic Contents
Given an array of integers (which may include positive numbers, negative numbers, and zeros), your task is to find and print the subarray that has the maximum sum.
If multiple subarrays have the same maximum sum, return the one that appears first. If the array is empty, return an empty result or appropriate message.
arr
of integers (positive, negative, or zero).max_sum = arr[0]
, current_sum = arr[0]
, start = 0
, end = 0
, and temp_start = 0
.current_sum + arr[i]
is less than arr[i]
, set current_sum = arr[i]
and temp_start = i
.arr[i]
to current_sum
.current_sum > max_sum
, update max_sum = current_sum
, start = temp_start
, end = i
.start
to end
gives the maximum sum.def max_subarray_with_indices(arr):
max_sum = current_sum = arr[0]
start = end = temp_start = 0
for i in range(1, len(arr)):
if arr[i] > current_sum + arr[i]:
current_sum = arr[i]
temp_start = i
else:
current_sum += arr[i]
if current_sum > max_sum:
max_sum = current_sum
start = temp_start
end = i
print("Maximum Sum:", max_sum)
print("Subarray:", arr[start:end+1])
# Sample Input
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_subarray_with_indices(arr)
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n) | Even in the best case, the algorithm must scan the entire array once to track subarray indices and sums. |
Average Case | O(n) | Each element is visited exactly once while updating the current and maximum subarray sums. |
Worst Case | O(n) | Regardless of input (positive, negative, mixed), the algorithm always performs a single pass through the array. |
O(1)
Explanation: The algorithm uses only a fixed number of variables (like max_sum, current_sum, start, end, temp_start) and no additional data structures, hence constant space.
⬅ Previous Topic
Maximum Subarray Sum using Kadane's AlgorithmNext Topic ⮕
Stock Buy and SellYou 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.