Maximum Subarray

Loading...LeetCode

Given an integer array nums, find the

subarraywith the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

• 1 <= nums.length <= 105

• -104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

You can solve this problem using the Kadane's algorithm, which is an efficient dynamic programming approach. Here's the JavaScript implementation:

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;
}

// Test cases
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])); // Output: 6
console.log(maxSubArray([1]));                    // Output: 1
console.log(maxSubArray([5,4,-1,7,8]));           // Output: 23

This implementation iterates through the array once, maintaining two variables: maxSum to keep track of the maximum sum found so far, and currentSum to keep track of the sum of the current subarray. At each iteration, it updates currentSum to be the maximum of the current element and the sum of the current element plus the previous sum. It also updates maxSum to be the maximum of maxSum and currentSum. Finally, it returns maxSum, which represents the largest sum of any subarray within the given array.