export function maxSubarraySumAtLeastK(nums: number[], k: number): number {
  const n = nums.length;

  // 1. Prefix sum
  const prefix = new Array(n + 1);
  prefix[0] = 0;

  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }

  // 2. Deque (guardará índices de prefix con valores crecientes)
  const deque: number[] = [];

  let result = -Infinity;

  for (let j = k; j <= n; j++) {
    const iCandidate = j - k;

    // Mantener deque con mínimos prefix
    while (
      deque.length > 0 &&
      prefix[deque[deque.length - 1]] >= prefix[iCandidate]
    ) {
      deque.pop();
    }

    deque.push(iCandidate);

    // El mejor i está en el frente
    const bestI = deque[0];

    result = Math.max(result, prefix[j] - prefix[bestI]);
  }

  return result;
}