Max subarray sum

2 snippets in Interview Prep

Also written as max sum subarray

DSAInterview Prep

Sliding Window

syntax

Maintain a window [left..right] and expand/shrink to satisfy a condition.
Fixed-size window: move both pointers together.
Variable-size window: expand right, shrink left when constraint violated.

example

// JavaScript — Max sum subarray of size k
function maxSumWindow(arr, k) {
  let windowSum = 0, maxSum = -Infinity;
  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];
    if (i >= k) windowSum -= arr[i - k];
    if (i >= k - 1) maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

# Python — Max sum subarray of size k
def max_sum_window(arr, k):
    window_sum = 0
    max_sum = float('-inf')
    for i in range(len(arr)):
        window_sum += arr[i]
        if i >= k:
            window_sum -= arr[i - k]
        if i >= k - 1:
            max_sum = max(max_sum, window_sum)
    return max_sum

output

max_sum_window([2,1,5,1,3,2], 3) → 9 (subarray [5,1,3])

Note Time O(n), Space O(1). Sliding window converts O(n*k) brute force to O(n). For variable-size windows (e.g., longest substring without repeats), use a hash set to track window contents. Always clarify: is the window fixed or variable size?

Kadane's Algorithm — Maximum Subarray

DSA · Arrays & Strings

syntax

Track current subarray sum. If it drops below 0, reset to 0.
At each step: currentSum = max(num, currentSum + num)
Keep a global max.

example

// JavaScript
function maxSubarraySum(arr) {
  let current = arr[0], best = arr[0];
  for (let i = 1; i < arr.length; i++) {
    current = Math.max(arr[i], current + arr[i]);
    best = Math.max(best, current);
  }
  return best;
}

# Python
def max_subarray_sum(arr):
    current = best = arr[0]
    for num in arr[1:]:
        current = max(num, current + num)
        best = max(best, current)
    return best

output

max_subarray_sum([-2,1,-3,4,-1,2,1,-5,4]) → 6 (subarray [4,-1,2,1])

Note Time O(n), Space O(1). Edge case: all negative numbers — algorithm still works since we initialize with arr[0]. To find the actual subarray indices, track start/end when best updates. Variant: maximum circular subarray uses total_sum - min_subarray.