
Description
The task is to find the maximum sum of a contiguous subarray within a given integer array. This problem is a classic example of using dynamic programming or a greedy approach to solve the maximum subarray sum efficiently.
Intuition
To solve this problem, we need to track the maximum sum of subarrays as we iterate through the array. The idea is to maintain a running sum of the current subarray and update the maximum sum whenever this running sum exceeds the previously recorded maximum. If the running sum drops below zero, we reset it to zero, since a negative running sum would not contribute positively to any future subarray.
Approach
- Initialization:
- Start by initializing
max_sum
to a very small value (negative infinity) to ensure any subarray sum will be greater. - Usecurrent_sum
to keep track of the sum of the current subarray. - Iteration:
- Loop through each element in the array, adding the element to
current_sum
. - Updatemax_sum
ifcurrent_sum
is greater than the currentmax_sum
. - Ifcurrent_sum
becomes negative, reset it to zero. This is because continuing with a negative sum would decrease the sum of any future subarray. - Result:
- After processing all elements,
max_sum
will hold the maximum sum of any contiguous subarray.
Complexity
Time Complexity:
O(n), where n is the number of elements in the array. The algorithm processes each element once, resulting in linear time complexity.
Space Complexity:
O(1), as only a fixed amount of extra space is used regardless of the input size. The algorithm uses a few variables to keep track of the current sum and maximum sum, but does not require additional space proportional to the input size.
Code
C++
class Solution {
public:
int maxSubArray(vector& nums) {
int max = INT_MIN;
int subArr = 0;
for (int i = 0; i < nums.size(); ++i) {
subArr += nums[i];
if (max < subArr) {
max = subArr;
}
if (subArr < 0) {
subArr = 0;
}
}
return max;
}
};
Python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float('-inf') # Initialize to the smallest possible value
current_sum = 0 # Variable to keep track of the current subarray sum
for num in nums:
current_sum += num
if current_sum > max_sum:
max_sum = current_sum
if current_sum < 0:
current_sum = 0
return max_sum
Java
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE; // Initialize to the smallest possible integer value
int subArr = 0; // Variable to keep track of the current subarray sum
for (int num : nums) {
subArr += num;
if (subArr > max) {
max = subArr;
}
if (subArr < 0) {
subArr = 0;
}
}
return max;
}
}
JavaScript
var maxSubArray = function (nums) {
let max = -Infinity
let subArr = 0
for (let i = 0; i <= nums.length - 1; ++i) {
subArr += nums[i]
if (max < subArr) {
max = subArr
}
if (subArr < 0) {
subArr = 0
}
}
return max
};