TOP 25 ALGORITMOS | Kadane's Array

A ideia do algoritmo de Kadane é percorrer o array da esquerda para a direita e, para cada elemento, encontrar a soma máxima entre todos os subarrays que terminam naquele elemento. O resultado será o máximo de todos esses valores.

📁 | Resumo

🤖 | Código

function maxSubarraySum(arr) {
  let res = arr[0];

  // Loop externo para ponto inicial do subarray
  for (let i = 0; i < arr.length; i++) {
      let currSum = 0;

      // Loop interno para ponto final do subarray
      for (let j = i; j < arr.length; j++) {
          currSum = currSum + arr[j];

          // Atualiza res se currSum for maior que res
          res = Math.max(res, currSum);
      }
  }

  return res;
}

🕰️ | Complexidade de Tempo
Como estamos percorrendo a matriz apenas uma vez, a complexidade de tempo será O(n).

📦 | Complexidade de Espaço
Como estamos percorrendo a matriz apenas uma vez, a complexidade de espaço será O(1).