[Codility] MaxDoubleSliceSum javascript

문제

app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

 

풀이

첫번째 생각

1. 전체의 부분합을 구한다.
2. A, C 를 뽑는 모든 경우의 수를 구해서 계산한다.
3. 부분합[C-1] - 부분합[A] 으로 A+1 ~ C-1 까지의 부분합 구한 후 이 사이를 B라고 생각하고 하나씩 빼보면서 답을 구한다.

=> A, C를 뽑는 조합은 nC2 로 N제한이 10만이어서 10만 * 10만 으로 쉽게 시간초과가 날 것 같다.

두번째 생각

1. 왼쪽에서 오른쪽 방향으로 Largest Sum Contiguous Subarray 을 구한다.
2. 오른쪽에서 왼쪽 방향으로 Largest Sum Contiguous Subarray 을 구한다.
3. B를 2~C-1이라고 생각하고 B-1까지 왼쪽에서 오른쪽방향의 LSCS 가 계산하고 B+1에서 N-1까지 오른쪽에서 왼쪽 방향으로 LSCS가 계산해서 for문을 한번 돈다.

=> 이렇게 하면 B를 지정해주는 for문만 돌면 되므로 O(N)만에 해결할 수 있었다.

코드

function solution(A) {
  let increaseArray = new Array(A.length).fill(0);
  let decreaseArray = new Array(A.length).fill(0);

  for (let i = 1; i < A.length - 1; ++i) {
    increaseArray[i] = Math.max(increaseArray[i - 1] + A[i], 0);
  }
  for (let i = A.length - 2; i > 0; --i) {
    decreaseArray[i] = Math.max(decreaseArray[i + 1] + A[i], 0);
  }
  let ans = -9999999;

  for (let i = 1; i < A.length - 1; ++i) {
    ans = Math.max(increaseArray[i - 1] + decreaseArray[i + 1], ans);
  }
  return ans;
}