881826. Maximum Sum Subarray
Medium
Maximum Sum Subarray
Summary
Given an array of integers, find the maximum sum of a contiguous subarray (a subarray that is continuous and does not contain gaps) within the given array. This problem involves dynamic programming and requires finding the maximum sum of all possible subsequences.
Detailed Explanation
The algorithm for this problem is based on Kadane's Algorithm, which finds the maximum sum of a subarray by scanning the array from left to right and keeping track of the maximum sum found so far. The time complexity of this algorithm is O(n), where n is the number of elements in the array.
Here is a step-by-step breakdown of the solution:
- Initialize
max_sumandcurrent_sumto 0. - Iterate through the array from left to right:
- For each element, calculate the maximum sum that can be obtained by including this element in the subarray (
current_sum + current_element) or starting a new subarray from this point (max_sum). - Update
max_sumif the calculated value is greater.
- For each element, calculate the maximum sum that can be obtained by including this element in the subarray (
- The maximum sum found is the answer.
Time complexity: O(n), where n is the number of elements in the array. Space complexity: O(1), as we only need to keep track of two variables.
Optimized Solutions
Java
public int maxSumSubarray(int[] arr) {
int max_sum = 0;
int current_sum = 0;
for (int num : arr) {
current_sum = Math.max(num, current_sum + num);
max_sum = Math.max(max_sum, current_sum);
}
return max_sum;
}