Given an integer array nums, find the subarray with the largest sum and return its sum.
Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Subarray [4,-1,2,1] has the largest sum = 6.
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4Kadane's Algorithm: keep a running sum; reset to 0 if it goes negative.
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.length; i++) {
// Either extend current subarray or start fresh
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}Time: O(n) · Space: O(1)