function solution(sequence) {
let answer = 0;
const n = sequence.length;
const f = new Array(n).fill().map((_, idx) => {
if (idx % 2) return -sequence[idx]
else return sequence[idx]
});
const dp = new Array(2).fill(0).map(() => new Array(n).fill(0));
dp[0][0] = f[0];
dp[1][0] = f[0];
for (let i = 1; i < n; i ++) {
dp[0][i] = Math.min(f[i], dp[0][i - 1] + f[i]);
dp[1][i] = Math.max(f[i], dp[1][i - 1] + f[i]);
}
let minVal = dp[0][0];
for (let i = 1; i < n; i++) {
if (dp[0][i] < minVal) {
minVal = dp[0][i];
}
}
let maxVal = dp[1][0];
for (let i = 1; i < n; i++) {
if (dp[1][i] > maxVal) {
maxVal = dp[1][i];
}
}
answer = Math.max(Math.abs(minVal), Math.abs(maxVal));
return answer;
}* 정답 알고리즘 - DP
문제 해석
1. 먼저 펄스수열을 곱해놓고 시작하자!
[1, -1, 1, -1 ...] 또는 [-1, 1, -1, 1, ...]을 곱해서 만든 수열을 탐색할 것이기 때문에 미리 입력받은 sequence에 [1, -1, 1, -1, ...]을 곱하여 생각합니다.
[-1, 1, -1, 1, ...]을 곱한 것은 단지 -1을 곱해주면 되는 것이기에 따로 생각해주지는 않습니다.
2. for문으로 탐색해볼까..
단순하게 for문을 이용한 탐색을 하게 되면
0번째 인덱스에서 시작하는 부분수열 총 n-1개
1번째 인덱스에서 시작하는 부분수열 총 n-2개
...
n-1번째 인덱스에서 시작하는 부분수열 총 1개
총 n(n-1)/2 가지를 탐색해야합니다. => 시간복잡도가 O(n^2)으로 효율성에 문제가 있습니다.
3. DP를 활용해보자!
위와 같은 이유로 DP를 활용하여 문제를 풀기로 하였습니다
풀이 방향
1.
const f = new Array(n).fill().map((_, idx) => {
if (idx % 2) return -sequence[idx]
else return sequence[idx]
});이 부분은 입력 된 sequence에 펄스 수열을 곱하는 부분입니다.
f라는 Array를 선언함과 동시에 map함수를 통해 짝수 번 째 인덱스에는 sequence값을 그대로 사용, 홀수 번 째 인덱스에는 sequence값에 -1을 곱한 값을 채워주었습니다
2.
앞서 말씀드렸듯이 [1, -1, 1, -1]인 펄스 수열과 [-1, 1, -1, 1]인 펄스 수열 두 가지를 모두 확인해야합니다.
때문에 DP 알고리즘에 사용 될 배열을 두 개로 만들었습니다.
const dp = new Array(2).fill(0).map(() => new Array(n).fill(0));
dp[0][0] = f[0];
dp[1][0] = f[0];3.
문제의 DP 알고리즘을 적용하는 방법입니다.
첫 번째 줄에는 f 배열에 있는 값과 dp 배열의 이전값을 더한 것과 f배열 값을 비교하여 작은 것을 택합니다.
예를 들어 보면
sequence = [2, 3, -6, 1, 3, -1, 2, 4]
f = [2, -3, -6, -1, 3, 1, 2, -4]
dp = [2, 0, 0, 0, 0, 0, 0, 0]
이 초기 상태입니다.
여기서 첫 번째 시행을 하면 dp[0]과 f[1] + dp[0]을 비교하여 더 큰 2를 선택합니다.
dp = [2, 2, 0, 0, 0, 0, 0, 0]
두 번째 시행을 하면 dp[1]과 f[2] + dp[1]을 비교하여 더 큰 2를 선택합니다.
dp = [2, 2, 2, 0, 0, 0, 0, 0]
세 번째 시행을 하면 dp[2]과 f[3] + dp[2]을 비교하여 더 큰 3을 선택합니다.
dp = [2, 2, 2, 3, 0, 0, 0, 0]
이렇게 채워나가게 되면 dp의 i 번째 인덱스가 뜻하는 바는 f의 i번째 인덱스를 끝으로 하는 연속 펄스 부분 수열 합의 최댓값이 됩니다.
f의 i번째 인덱스를 끝으로 하는 연속 펄스 부분 수열 합의 최솟값을 구하기 위해서는 시행마다 더 작은 값을 선택해주면 됩니다.
4.
let minVal = dp[0][0];
for (let i = 1; i < n; i++) {
if (dp[0][i] < minVal) {
minVal = dp[0][i];
}
}
let maxVal = dp[1][0];
for (let i = 1; i < n; i++) {
if (dp[1][i] > maxVal) {
maxVal = dp[1][i];
}
}이 코드를 통해 dp의 첫 번째 줄에서 최솟값을, 두 번째 줄에서 최댓값을 찾습니다.
const minVal = Maht.max(...dp[0])으로 하지 않는 이유는 dp[0]의 길이가 매우 길 경우 자바스크립트 함수는 ...dp[0]과 같은 spread구문을 iterable객체의 요소의 값을 모두 각각의 입력변수로 처리하여 stack over flow에러가 생길 수 있기 때문입니다. 즉, dp[0]의 길이가 500000만일 경우 Math.max(...dp[0])은 함수를 500000만 번 호출하는 것과 동일한 일을 처리하는 것입니다.
