Maximum Subarray Sum at Most K

Reported in interviews at Squarepoint Capital

Problem statement

Given an integer array (values may be negative) and a target $k$, find the maximum sum of a non-empty contiguous subarray whose total does not exceed $k$. If no such subarray exists, return None (e.g. $nums = [5]$, $k = 2$).

Constraints:

  • $1 \le n \le 10^5$
  • values and $k$ can be negative.

Examples:

  • Input: $nums = [2, 2, -1]$, $k = 3$. Output: $3$ (the whole array sums to $3 \le 3$).
  • Input: $nums = [2, 1, -3, 4]$, $k = 2$. Output: $2$ (the best total not exceeding $2$ is $2$, achieved by $[2]$ and by $[1, -3, 4]$).
Show hint

How can the sum of any contiguous subarray be written using running totals?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems