Back to DSA
Maximum Subarray
mediumAn integer array is given. Find a contiguous subarray (containing at least one element) that has the largest sum among all possible contiguous subarrays, and return that sum.
Examples
Example 1:
Input:
nums = [3,-1,4,-2,5,-3,2]Output:
9Explanation: The subarray [3,-1,4,-2,5] sums to 9, which is the maximum achievable.
Example 2:
Input:
nums = [-4,-2,-8,-1]Output:
-1Explanation: All values are negative. The best subarray is the single element -1.
Hints
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0], curSum = nums[0];
for (int i = 1; i < nums.length; i++) {
curSum = Math.max(nums[i], curSum + nums[i]);
maxSum = Math.max(maxSum, curSum);
}
return maxSum;
}
}Time complexity
O(n)Space complexity
O(1)