Se você gosta de desafios de lógica e algoritmos para aquecer os motores durante a semana, provavelmente conhece a newsletter da Cassidoo, onde toda semana ela envia uma questão de entrevista técnica.

Nesse meu repositório é possível encontrar as minhas soluções dos desafios anteriores: ebdonato/cassidoo-questions

Questão da Semana

Dado um vetor de inteiros, encontre o subvetor contíguo que possui a maior soma e retorne essa soma. Um subvetor deve conter pelo menos um elemento. Se todos os elementos forem negativos, retorne o maior (menos negativo) valor.

Exemplos

> maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
6
> maxSubarraySum([5])
5
> maxSubarraySum([-1, -2, -3, -4])
-1
> maxSubarraySum([5, 4, -1, 7, 8])
23

Minha Solução

/**
 * Finds the maximum sum of a contiguous subarray in an array of numbers.
 * Implements Kadane's algorithm.
 * @param arr - The array of numbers to search
 * @returns The maximum sum of a contiguous subarray
 */
export function maxSubarraySum(arr: number[]): number {
  let cur = arr[0];

  return arr.reduce(
    (max, v, i) =>
      i === 0 ? max : ((cur = Math.max(v, cur + v)), Math.max(max, cur)),
    arr[0],
  );
}