문제
입력: 정수 배열 출력: 연속된 부분배열의 최대합
입출력 예시
1
2
3
4
5
6
7
8
9
10
11
let output = LSCS([1, 2, 3]);
console.log(output); // --> 6
output = LSCS([1, 2, 3, -4]);
console.log(output); // --> 6 ([1, 2, 3])
LSCS([1, 2, 3, -4, 5]);
console.log(output); // --> 7 ([1, 2, 3, -4, 5])
LSCS([10, -11, 11]);
console.log(output); // --> 11 ([11])
분석
처음부터 하나씩 탐색을 할 때 음수를 만나는 경우 어떻게 처리할 것인가가 문제의 핵심이다.
첫 두 수가 [3, -2]라고 하자.
현재로서는 -2를 선택할 이유가 없다. 왜냐하면 -2를 합하면 2를 빼는 것과 같기 때문이다.
만약 다음 수가
- 음수라면 -2를 택할 이유는 더더구나 없다.
- 1이라면 어떨까. [3, -2, 1]이 되고 달라질 것은 없다. 1까지 선택하는 경우 최대합이 2가 되면서 첫 수 3만 선택한 것보다 작기 때문이다.
- 3이라면 다르다. [3, -2, 3]이 되고 이때에는 마지막 3까지 포함하는 것이 더 좋은 선택이 된다. 최대합이 4가 되며 첫 수 3만 선택했던 것보다 큰 합이 된다.
이상의 사실에서 알 수 있는 것은
직전까지의 부분최대합을 알고 있어야 한다는 것이다. 직전까지의 부분합과 현재의 값 중 큰 값을 알아야 한다. 첫 수 3의 경우 부분최대합은 3이다.
[3, -2]의 부분최대합은 3 + (-2)과 -2 중에서 큰 값이 1이 된다. 연속부분배열의 최대합은 3이다.
다음 [3, -2, 1]의 부분최대합은 1 + 1과 1 중에서 큰 값인 2가 된다. 이제 부분최대합 2와 직전의 연속부분배열의 최대합 3을 비교해 큰 값을 택한다. 결과 연속부분배열의 최대합은 3이다.
이런 식으로 부분최대합을 구해놓는 과정이 필요하다.
코드 JavaScript
1
2
3
4
5
6
7
8
9
10
const LSCS = function (arr) {
let Sum = arr[0];
let subSum = arr[0];
for (let i = 1; i < arr.length; i++) {
subSum = Math.max(subSum + arr[i], arr[i]);
Sum = Math.max(Sum, subSum);
}
return Sum;
};
마무리
실제 코드는 매우 짧다.
DP 알고리즘 문제다. 부분문제의 결괏값으로부터 전체문제의 결괏값을 알 수 있기 때문이다. bottom-up 방식으로 하면서 DP 문제에서 흔하게 보는 저장배열을 사용하지 않은 특이한 케이스이다. 계산의 반복을 막기 위해 저장배열을 사용하는 것이 DP 알고리즘의 핵심 중 하나인데, 그 과정이 없으니 이 문제는 DP라고 봐야하는 지 모르겠다. 어쨌든 알고리즘 문제에서 기본이지만 어려운 ‘흔한’ 문제이다.