A maximal subarray

Input er et array af tal, f.eks. arr = [1, -2, 3, 4, -9, 6].

Opgaven er: find det sammenhængende delarray af arr med den maksimale sum af elementer.

Skriv funktionen getMaxSubSum(arr), der returnerer den sum.

For eksempel:

          getMaxSubSum([-1, 2, 3, -9]) == 5 (summen af de markerede elementer)
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 (tag det hele)
        

Hvis alle elementer er negative, betyder det, at vi ikke tager nogen (delarrayet er tomt), så summen er nul:

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

Prøv at tænke på en hurtig løsning: O(n²) eller endda O(n), hvis du kan.

Åbn en sandbox med tests.

Langsom løsning

Vi kan beregne alle mulige delsummer.

Den simpleste måde er at tage hvert element og beregne summen af alle delarrays, der starter fra det. For eksempel, for [-1, 2, 3, -9, 11]:

          // Startende fra -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// Startende fra 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// Startende fra 3:
3
3 + (-9)
3 + (-9) + 11

// Startende fra -9
-9
-9 + 11

// Startende fra 11
11
        

Koden er faktisk en indlejret løkke: den ydre løkke går over array-elementerne, og den indre tæller delsummer, der starter med det aktuelle element.

function getMaxSubSum(arr) {
  let maxSum = 0; // hvis vi ikke tager nogle elementer, vil nul blive returneret

  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

Løsningen har en tidskompleksitet på O(n²). Med andre ord, hvis vi fordobler størrelsen på arrayet, vil algoritmen tage fire gange så lang tid.

For store arrays (1000, 10000 eller flere elementer) kan sådanne algoritmer føre til alvorlig langsommelighed.

Hurtig løsning

Lad os gå igennem arrayet og holde den nuværende delsum af elementer i variablen s. Hvis s bliver negativ på et tidspunkt, så sæt s=0. Maksimum af alle sådanne s vil være svaret.

Hvis beskrivelsen er for vag, så se venligst koden, den er kort nok:

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

  for (let item of arr) { // for hvert item af arr
    partialSum += item; // læg item til partialSum
    maxSum = Math.max(maxSum, partialSum); // husk maksimum
    if (partialSum < 0) partialSum = 0; // nul hvis negativ
  }

  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

Algoritmen kræver præcis 1 gennemgang af arrayet, så tidskompleksiteten er O(n).

Du kan finde mere detaljeret information om algoritmen her: Maximum subarray problem. Hvis det stadig ikke er indlysende, hvorfor det virker, så prøv at følge algoritmen på eksemplerne ovenfor, se hvordan den fungerer, det er ofte bedre end ord.

Åbn løsningen med tests i en sandbox.