Problem Statement
You are given an integer array arr[]. Your task is to find the maximum sum of a contiguous subarray containing at least one element.
A subarray is defined as a continuous portion of an array.
Examples
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 -2.
Example 3:
Input: arr = [5, 4, 1, 7, 8]
Output: 25
Explanation: The subarray [5, 4, 1, 7, 8] has the largest sum 25.
Constraints
1 ≤ arr.size() ≤ 10^5
-10^4 ≤ arr[i] ≤ 10^4
These constraints imply that a brute-force O(n²) solution will not work for large arrays. We need an O(n) solution, which is exactly what Kadane’s Algorithm provides.
Steps:
Initialize current_max = arr[0] and max_so_far = arr[0].
Traverse the array starting from index 1:
Update current_max = max(arr[i], current_max + arr[i]) - either extend the current subarray or start a new one
Update max_so_far = max(max_so_far, current_max) - update the overall maximum sum
After traversing the array, max_so_far contains the maximum sum of any contiguous subarray.
Python Code
class Solution:
def maxSubarraySum(self, arr):
# Initialize the first element as the starting max
max_so_far = arr[0]
current_max = arr[0]
# Traverse the array starting from index 1
for i in range(1, len(arr)):
current_max = max(arr[i], current_max + arr[i])
max_so_far = max(max_so_far, current_max)
return max_so_far
Example INPUT AND OUTPUT
arr1 = [2, 3, -8, 7, -1, 2, 3]
arr2 = [-2, -4]
arr3 = [5, 4, 1, 7, 8]
ob = Solution()
print(ob.maxSubarraySum(arr1))
Output: 11
print(ob.maxSubarraySum(arr2)) #
Output: -2
print(ob.maxSubarraySum(arr3)) #
Output: 25
Explanation
At every element, the algorithm decides whether to continue the current subarray or start a new one.
max_so_far always keeps track of the maximum sum encountered so far.
The solution runs in O(n) time and uses O(1) space, making it efficient for large inputs.
Top comments (0)