Dare2Solve
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.
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.
Initialization:
max_sum
to a very small value (negative infinity) to ensure any subarray sum will be greater.current_sum
to keep track of the sum of the current subarray.Iteration:
current_sum
.max_sum
if current_sum
is greater than the current max_sum
.current_sum
becomes negative, reset it to zero. This is because continuing with a negative sum would decrease the sum of any future subarray.Result:
max_sum
will hold the maximum sum of any contiguous subarray.O(n), where n is the number of elements in the array. The algorithm processes each element once, resulting in linear time 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.
class Solution {
public:
int maxSubArray(vector<int>& 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;
}
};
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
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;
}
}
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
};