[LeetCode] 53. Maximum Subarray

Table of Contents

Description

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: 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.

Brute Force Approach

We can considers all possible subarrays and calculates their sums to find the maximum. This method is simple but inefficient for large arrays and will result in a timeout when you submitted.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let max = -Infinity;

  for (let start = 0; start < nums.length; start++) {
    let sum = 0;

    for (let end = start; end < nums.length; end++) {
      sum += nums[end];
      max = Math.max(max, sum);
    }
  }

  return max;
};

Optimized Approach

We can use Kadane’s Algorithm to efficiently find the maximum subarray sum in a single loop. By keeping track of the best sum ending at each position, we can always determine the largest possible subarray sum without checking every possibility.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let max = -Infinity;

  for (let i = 0, maxEndingHere = -Infinity; i < nums.length; i++) {
    maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);

    max = Math.max(maxEndingHere, max);
  }

  return max;
};

Complexity Analysis

Time Complexity

• Brute Force Approach: $O(n^2)$, where $n$ is the length of the array. We check all possible subarrays using two nested loops.
• Optimized Approach (Kadane’s Algorithm): $O(n)$, where $n$ is the length of the array. We iterate through the array once, performing constant-time operations for each element.

Space Complexity

• Brute Force Approach: $O(1)$, as only a few variables are used for tracking sums and the maximum.
• Optimized Approach (Kadane’s Algorithm): $O(1)$, as we only use a few variables to keep track of the current and maximum sums.