Find the contiguous subarray with the largest sum.
Input: nums=[-2,1,-3,4,-1,2,1,-5,4] → Output: 6. Subarray [4,-1,2,1] has sum 6.
Input: nums=[1] → Output: 1
Kadane's algorithm: track current sum and global max.
- Initialize curSum = nums[0], maxSum = nums[0]
- For each next element: curSum = max(num, curSum+num)
- Update maxSum = max(maxSum, curSum)
- Return maxSum
public int maxSubArray(int[] nums) {
int curSum = nums[0], maxSum = 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)