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).