Codility Lesson 9 - MaxSliceSum

문제 설명

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어집니다. 0 ≤ P ≤ Q < N인 한 쌍의 정수(P, Q)를 배열 A의 슬라이스라고 하며, 한 슬라이스(P, Q)의 합은 A[P] + A[P+1] + … + A[Q]의 총합입니다. + A[Q]입니다.

함수를 작성합니다:

function solution(A);

이 함수는 N개의 정수로 구성된 배열 A가 주어졌을 때 A의 모든 슬라이스의 최대 합을 반환합니다.

예를 들어 배열 A가 주어졌을 때

a[0] = 3 a[1] = 2 a[2] = -6
a[3] = 4 a[4] = 0

이면 함수는 5를 반환해야 합니다:

• (3, 4)는 합이 4인 A의 조각입니다,
• (2, 2)는 합이 -6인 A의 조각입니다,
• (0, 1)은 합이 5인 A의 조각입니다,
• A의 다른 어떤 부분도 (0, 1)보다 큰 합을 갖지 않습니다.

다음 가정에 대한 효율적인 알고리즘을 작성하십시오:

• N은 [1..1,000,000] 범위 내의 정수입니다;
• 배열 A의 각 요소는 [-1,000,000..1,000,000] 범위 내의 정수입니다;
• 결과는 [-2,147,483,648..2,147,483,647] 범위 내의 정수가 됩니다.

문제 접근

배열을 순회하면서 현재까지 더한값이 max 값보다 큰지 작은지 비교해간다.

1. 배열을 순회하면서 현재까지 더한 값(sum) vs 현재 값(A[i]) 비교하여 큰값을 sum 재할당.
2. 현재 가장큰값과 현재 sum 값을 비교하여 큰값을 다시 재할당한다.

function solution(A) {
  if (A.length === 1) {
    return A[0]
  }

  let result = A[0]
  let sum = A[0]

  for (let i = 1; i < A.length; i++) {
    sum = Math.max(A[i], sum + A[i])
    result = Math.max(result, sum)
  }

  return result
}