Viewing: fa.javascript.info

arr = [1, -2, 3, 4, -9, 6].

: arr .

getMaxSubSum(arr) .

          getMaxSubSum([-1, 2, 3, -9]) == 5 (  )
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 (   )
        

( ) :

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

: O(n2) O(n) .

sandbox .

[11 ,9- ,3 ,2 ,1-]:

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

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

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

// -9  :
-9
-9 + 11

// -11  :
-11
        

: .

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

  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

O(n2) 4 .

(1000 10000 ) .

s . s s=0 . s .

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

  for (let item of arr) { //    
    partialSum += item; //   partialSum   
    maxSum = Math.max(maxSum, partialSum); //      
    if (partialSum < 0) partialSum = 0; //       
  }

  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

1 O(n) .

: . .

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

  for (let item of arr) {
    partialSum += item;
    maxSum = Math.max(maxSum, partialSum);
    if (partialSum < 0) partialSum = 0;
  }
  return maxSum;
}
        

sandbox.