Leetcode 53: Maximum Subarray in JavaScript

The Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

A subarray is a contiguous(side-by-side) non-empty sequence of elements within an array. It is a part of the array where the numbers are next to each other. You cannot skip elements in between.

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.

The Thought Process

We can use Dynamic Programming to solve this problem. Dynamic Programming (DP) is just a way of solving a big problem by breaking it into smaller steps, remembering the answers, and reusing them so we don’t repeat work.

In this problem, we ask ourselves for every index in the array:

"What is the largest sum of a subarray that ends exactly at this index?"

If we know the largest sum ending at the previous index, we can decide:

• Start fresh at the current number (nums[i]) if the previous sum was negative
• Or continue the subarray from before by adding the current number

This gives our DP rule:

currentMax = max(nums[i], nums[i] + currentMax(previous))

We also keep track of the biggest currentMax we’ve seen so far — that’s our answer.

The solution

const maxSubArray = (nums)=> {
  let maxSum = nums[0];
  let currentMax = 0;

  for (let i = 0; i < nums.length; i++) {
    currentMax = Math.max(nums[i], currentMax + nums[i]);
    let currentMaxSum = maxSum;

    if (currentMax > maxSum) {
      maxSum = currentMax;
    } else {
      maxSum = currentMaxSum;
    }
  }

  return maxSum;
};

• Time Complexity: O(n). You loop through the array once (for (let i = 0; i < nums.length; i++)), so the work grows linearly with n.
• Space Complexity: O(1). You only use a fixed number of variables (maxSum, currentMax, currentMaxSum) regardless of the size of the input array. No extra arrays or data structures are created.

Comments

[Collins Dada]

I understand 50% of this topic. But keep up the great work tochi 🖤

[Tochi]

Thank you! If you need guidance, hit me up.