blind-75

Maximum Subarray

Best Case: The best case occurs when all numbers are positive.
Worst Case: The worst case occurs when all numbers are negative.

Approach:

1. Use Kadane’s algorithm to track maximum subarray sums by iterating through the array and updating sums.

Explanation to Interviewer:
“I would implement Kadane’s algorithm which allows me to maintain a running sum and reset it whenever it becomes negative while keeping track of the maximum found so far.”

Code Implementation:

JavaScript:

function maxSubArray(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

const nums = [-2,1,-3,4,-1,2,1,-5,4];
console.log(maxSubArray(nums)); // Output: 6

Python:

def max_sub_array(nums):
    max_sum = current_sum = nums[0]

    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)

    return max_sum

nums = [-2,1,-3,4,-1,2,1,-5,4]
print(max_sub_array(nums)) # Output: 6