[TIL] 알고리즘 - 최대부분배열합

Today I Learned

문제

정수 배열이 주어졌을 때, 연속한 숫자들로 이루어진 부분 배열 중 합이 최대가 되는 경우를 구하시오.

내가 시도한 풀이

1st attempt : 생각나는 대로 시간복잡도를 생각하지 않고 풂

const getMaxSumOfSubArray = function (arr) {
  let size = arr.length;
  let max = arr[0];
  for (let i = 0; i < size; i++) {
    let sum = 0;
    for (let j = i; j < size; j++) {
      sum += arr[j];
      max = Math.max(max, sum);
    }
  }
  return max;
};

-> 문제점 : 배열 길이가 커지면 실행 시간이 초과됨

2nd attempt : 시간복잡도를 개선함

-> 시간 복잡도 개선

const getMaxSumOfSubArray = function (arr) {
  const cache = new Array(arr.length);
  cache[0] = arr[0];
  for (let i = 1; i < arr.length; i++) {
    let max = Math.max(0, cache[i-1] + arr[i]);
    cache[i] = max;
  }
  return Math.max(...cache);
}

-> 문제점 : 실행 시간이 초과되지는 않지만 음수만 있는 배열이 통과가 안됨

3rd attempt : 레퍼런스를 보고 새로 풂

-> i-1번째 까지의 합에 arr[i]를 더하는 것보다 arr[i]가 크다면 앞의 것을 버리고 arr[i]를 취한다

const getMaxSumOfSubArray = function (arr) {
  const cache = new Array(arr.length);
  cache[0] = arr[0];
  for (let i = 1; i < arr.length; i++) {
    let max = Math.max(cache[i-1] + arr[i], arr[i]);
    cache[i] = max;
  }
  return Math.max(...cache);
}

-> alt. cache를 사용하지 않고도 풀 수 있다.

const getMaxSumOfSubArray = function (arr) {
  let thisSum = arr[0];
  let maxSum = arr[0];
  for (let i = 1, n = arr.length; i < n; i++) {
    thisSum = Math.max(thisSum + arr[i], arr[i]);
    maxSum = Math.max(thisSum, maxSum);
  }
  return maxSum;
};