Maximum Subarray - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';

function visMainFunction(inputNums) {
    initClassProperties();

    startBatch();
    const nums = VisArray.from(inputNums);
    let maxEndingAtIndex = nums[0];
    let maxSoFar = maxEndingAtIndex;
    let index = 1;

    makeVisVariable(index).registerAsIndexPointer(nums, CURRENT);
    makeVisVariable(maxEndingAtIndex).options({label: 'maxEndingAtIndex'}).createVis(true);
    makeVisVariable(maxSoFar).options({label: 'maxSoFar'}).createVis(true);
    endBatch();

    explanationAndColorPaletteNotifications();

    // Pre-loop status + decision rule
    notification(`
      ▶️ <b>Initialization complete</b><br/>
      <ul style="margin:6px 0 0 16px;">
        <li><code>maxEndingAtIndex = nums[0] = ${nums[0]}</code> (best subarray ending at index 0)</li>
        <li><code>maxSoFar = ${maxSoFar}</code> (global best so far)</li>
      </ul>
      From index ${makeColoredSpan(index, CURRENT_COLOR)} onward, at each step we either <b>extend</b> the current subarray
      or <b>start a new subarray</b> at the current index, implemented as <code>maxEndingAtIndex = max(maxEndingAtIndex, 0) + nums[i]</code>.
    `);

    while (index < nums.length) {
        startPartialBatch();
        const num = nums[index];

        notification(`
          🔎 <b>Decision at index</b> ${makeColoredSpan(index, CURRENT_COLOR)}:<br/>
          ${
            maxEndingAtIndex >= 0
              ? `Since <code>maxEndingAtIndex</code> is non-negative, <b>extend</b> the current subarray:<br/>
                 <code>maxEndingAtIndex + nums[i]</code> = <b>${maxEndingAtIndex}</b> + <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> = <b>${maxEndingAtIndex + num}</b>.`
              : `Since <code>maxEndingAtIndex</code> is negative, <b>reset</b> it to <code>0</code> and <b>start a new subarray</b> at the current index:<br/>
                 <code>0 + nums[i]</code> = <b>${makeColoredSpan(num, CURRENT_COLOR)}</b>.`
          }<br/>
          Update with the formula: <code>maxEndingAtIndex = max(maxEndingAtIndex, 0) + nums[i]</code>.
        `);

        maxEndingAtIndex = Math.max(maxEndingAtIndex, 0) + num;

        notification(`
          📈 <b>Update global best</b> (<code>maxSoFar</code>)<br/>
          Compare current <b>maxSoFar</b> = <b>${maxSoFar}</b> with <b>maxEndingAtIndex</b> = <b>${maxEndingAtIndex}</b>.<br/>
          Set <b>maxSoFar = ${Math.max(maxSoFar, maxEndingAtIndex)}</b>.
        `);
        maxSoFar = Math.max(maxSoFar, maxEndingAtIndex);

        index += 1;
        endBatch();
    }

    notification(`✅ <b>Result:</b> The sum of the subarray with the largest sum is <b>${maxSoFar}</b>.`);
    return maxSoFar;
}

function explanationAndColorPaletteNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Palette Guide</b><br/><br/>
        • ${makeColoredSpan("Blue background", CURRENT_COLOR)} → <b>Current index pointer and value</b><br/>
    `);
}

function initClassProperties() {
    setClassProperties(CURRENT, {
        backgroundColor: CURRENT_COLOR
    })
}

Approach

Goal

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Key Idea (Intuition)

At each index, we decide whether to extend the best subarray ending at the previous index or start a new subarray at the current index. If the running sum up to the previous index is negative, then starting fresh at the current index yields a larger value for maxEndingAtIndex than extending the negative sum. Otherwise, it is better to extend the previous subarray by adding the current element.

Initialization

maxEndingAtIndex = nums[0] — best subarray sum that ends at index 0.
maxSoFar = maxEndingAtIndex — global best sum seen so far.
Start traversal at i = 1.

Traversal

For each index i from 1 to n - 1:

Update the best ending here:
maxEndingAtIndex = max(maxEndingAtIndex, 0) + nums[i]
(If maxEndingAtIndex was negative, reset to 0 to start a new subarray at i; otherwise, extend the previous subarray.)
Update the global best:
maxSoFar = max(maxSoFar, maxEndingAtIndex)

Return

After the loop, return maxSoFar as the maximum subarray sum.

Time Complexity

We make a single pass over the array, performing O(1) work at each index. Therefore, the time complexity is O(n), where n is the length of the array.

Space Complexity

The algorithm maintains only a constant number of variables (maxEndingAtIndex, maxSoFar, and index). No additional data structures are used. Therefore, the space complexity is O(1).

Input-1

Maximum Subarray - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Goal

Key Idea (Intuition)

Initialization

Traversal

Return

Time Complexity

Space Complexity