Viewing: es.javascript.info

La entrada es un array de nmeros, por ejemplo arr = [1, -2, 3, 4, -9, 6].

La tarea es encontrar, dentro de arr, el subarray de elementos contiguos que tenga la suma mxima.

Escribe la funcin getMaxSubSum(arr) que devuelva el resultado de tal suma.

Por ejemplo:

          getMaxSubSum([-1, 2, 3, -9]) == 5 (la suma de items resaltados)
getMaxSubSum([2, -1, 2, 3, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, 11]) == 11
getMaxSubSum([-2, -1, 1, 2]) == 3
getMaxSubSum([100, -9, 2, -3, 5]) == 100
getMaxSubSum([1, 2, 3]) == 6 (toma todo)
        

Si todos los elementos son negativos, no toma ninguno (el subarray queda vaco) y la suma es cero:

getMaxSubSum([-1, -2, -3]) = 0

Trata de pensar en una solucin rpida: O(n2), o incluso O(n) si puedes.

Abrir en entorno controlado con pruebas.

solucin

Solucin lenta

Podemos calcular todas las subsumas.

La forma ms simple es tomar cada elemento y calcular las sumas de todos los subarrays que comienzan con l.

Por ejemplo, para [-1, 2, 3, -9, 11]:

          // Comenzando desde -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// Comenzando desde 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// Comenzando desde 3:
3
3 + (-9)
3 + (-9) + 11

// Comenzando desde -9
-9
-9 + 11

// Comenzando desde 11
11
        

El cdigo es un bucle anidado. El bucle externo itera sobre los elementos del array, y el interno cuenta subsumas comenzando con cada uno de ellos.

function getMaxSubSum(arr) {
  let maxSum = 0; // si no obtenemos elementos, devolver cero

  for (let i = 0; i < arr.length; i++) {
    let sumFixedStart = 0;
    for (let j = i; j < arr.length; j++) {
      sumFixedStart += arr[j];
      maxSum = Math.max(maxSum, sumFixedStart);
    }
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

La solucin tiene una complejidad 2 en notacin Landau O(n2) (coste respecto al tiempo). Es decir, si multiplicamos el tamao del array por 2, el tiempo del algoritmo se multiplicar por 4.

Para arrays muy grandes (1000, 10000 o ms items) tales algoritmos llevarn a una severa lentitud.

Solucin rpida

Recorramos el array y registremos la suma parcial actual de los elementos en la variable s. Si s se vuelve cero en algn punto, le asignamos s=0. El mximo entre todas las sumas parciales s ser la respuesta.

Si la descripcin te resulta demasiado vaga, por favor mira el cdigo. Es bastante corto:

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) { // por cada item de arr
    partialSum += item; // se lo suma a partialSum
    maxSum = Math.max(maxSum, partialSum); // registra el mximo
    if (partialSum < 0) partialSum = 0; // cero si se vuelve negativo
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0

El algoritmo requiere exactamente una pasada, entonces la complejidad es O(n).

Puedes encontrar informacin ms detallada acerca del algoritmo: Subvector de suma mxima. Si an no es obvio cmo funciona, traza el algoritmo en los ejemplos de arriba y observa cmo trabaja, es mejor que cualquier explicacin.

Abrir la solucin con pruebas en un entorno controlado.

Subarray mximo

Solucin lenta

Solucin rpida