Maximum subarray

• Kadane
• javascript_trick To swap numbers use [a, b] = [b, a], works like a charm.
• javascript_trick For minimum element use Number.MIN_VALUE, this value is equal to 5e-324.
• MIN_VALUE in JavaScript represents the smallest positive numeric value that can be represented in the language. It is a positive value close to zero, but not actually zero. The value is approximately 5e-324. This constant is often used when working with numbers and want to represent the smallest positive value that can be held by the data type.

Explain to interviewer like this

The algorithm used in the provided JavaScript code is called Kadane’s algorithm, and its purpose is to find the maximum subarray sum in a given array of numbers. Here’s an intuition behind the algorithm:

1. Initialization:

   • cur_sum: This variable keeps track of the sum of the current subarray.
   • max_sum: This variable keeps track of the maximum subarray sum found so far.

2. Iterating through the array:

   • The loop starts from index 1 (assuming the first element at index 0 is already considered).
   • For each element in the array, cur represents the current element being considered.

3. Updating cur_sum and max_sum:

   • cur_sum is updated by choosing the maximum value between the current element cur and the sum of the current subarray plus the current element (cur_sum + cur).
   • max_sum is updated by choosing the maximum value between the current max_sum and the updated cur_sum.

4. Handling negative values:

   • If cur_sum becomes negative, it is reset to 0. This is because including a negative sum in the current subarray would only decrease the total sum.

5. Result:

   • The final max_sum represents the maximum subarray sum.

The idea behind Kadane’s algorithm is that at each step, you decide whether to extend the current subarray or start a new subarray from the current element. By keeping track of the current subarray sum (cur_sum) and the maximum sum found so far (max_sum), the algorithm efficiently identifies the maximum subarray sum in a single pass through the array.

Code

• Transclude of maximum-subarray.js

Attempt

function maxSum(nums) {
	let cur_sum = nums[0];
	let max_sum = nums[0];
 
	for (let i = 1; i < nums.length; i++) {
		let cur = nums[i];
		cur_sum += cur;
		max_sum = Math.max(cur_sum, cur);
		if (cur_sum > max_sum) {
			max_sum = cur_sum;
		}
		if (cur_sum < 0) {
			cur_sum = 0;
		}
	}
 
}