public static int maxSubArray(int[] nums) {
	int maxSoFar = nums[0];
	int maxEndingHere = nums[0];
 
	for (int i = 1; i < nums.length; ++i) {
		maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
		maxSoFar = Math.max(maxSoFar, maxEndingHere);
	}
 
	return maxSoFar;
}

Limitation of the Algorithm

So, remember to use modified Kadane's algorithm, when the array contains only negative numbers. Original Kadane's algorithm will return the value of the largest negative element rather than a sum, because the algorithm is designed to look for positive contiguous sequences. This may or may not be desired, depending on whether empty subarrays with a sum of 0 are considered valid.

16:["$","div",null,{"className":"max-w-7xl mx-auto

Related Tags