문제

배열 내에서 원소합이 가장 큰 sub배열 찾기

분석

어려운 문제는 아니지만 O(n)으로 풀 수 있는 아이디어를 떠올리기는 쉽지 않았다.

• 앞에서부터 쭉 더하다가 그 합이 음수가 되면 버리고 다시 시작!

코드

모든 배열의 원소가 양수일 때

const solution = A => {
  let maxEnding = 0, maxSlice = 0;

  for(let num of A){
    maxEnding = Math.max(0, maxEnding+num);
    maxSlice = Math.max(maxEnding, maxSlice);
  }

  return maxSlice;
}

배열의 원소가 양수, 음수일 때

const solution = A => {
  let maxSum=A[0];
  let maxSlice = A[0];
  for(let i=1; i<A.length; i++){
    maxSum = Math.max(maxSum+A[i], A[i]);
    maxSlice = Math.max(maxSum, maxSlice);
  }

  return maxSlice;
}

각자의 배열합의 합이 가장 큰 두개의 slice 찾기

const solution = A => {
  let len = A.length;

  let leftSliceSum = new Array(len).fill(0);
  let rightSliceSum = new Array(len).fill(0);

  for(let i=1; i<len-2; i++){
    leftSliceSum[i] = Math.max(0, leftSliceSum[i-1]+A[i]);
  }
  for(let i=len-2; i>=2; i--){
    rightSliceSum[i] = Math.max(0, rightSliceSum[i+1]+A[i]);
  }

  let result = Number.NEGATIVE_INFINITY;

  for(let i=1; i<len-1; i++){
    result = Math.max(result, leftSliceSum[i-1]+rightSliceSum[i+1]);
  }
  
  return result;
}