Problem
Given an integer arraynums, find the contiguous subarray with the largest sum and return that sum.
Example(s)
Consider the following example to understand the expected input and output.Input
nums = [-2,1,-3,4,-1,2,1,-5,4]Output
6Explanation
Maximum subarray = [4,-1,2,1]
4 + (-1) + 2 + 1 = 6
Solution
This problem can be solved optimally using Kadane's Algorithm.As we move through the array, we maintain the sum of the current subarray. For each element, we have two choices: extend the current subarray by adding the element, or start a new subarray from the current element.
If extending the current subarray produces a smaller sum than starting from the current element, we start a new subarray. This allows us to discard a previous subarray whose negative contribution would reduce any future sum.
We also maintain
maxSum, which stores the largest subarray sum found so far.
public int maxSubArray(int[] nums) {
int currentSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
// Start new or extend the current subarray.
currentSum = Math.max(nums[i], currentSum + nums[i]);
// Update the maximum sum.
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
Complexity
Each element is processed exactly once, resulting inO(n) time complexity. Only two variables are used, requiring O(1) extra space.