[Algorithm] 연속 펄스 부분 수열의 합

📋 문제

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000
  
  • sequence의 원소는 정수입니다.

 

입출력 예

[2, 3, -6, 1, 3, -1, 2, 4]

10

✏️ 풀이

처음 접근 방법은 배열을 하나 선언하고 인접한 두수를 더해서 선언했던 배열에 넣으며 배열의 길이가 1일때까지 반복하는 로직을 생각했다. 하지만 생각해보니 [1, 2, 3]이라는 배열이 있는 경우 [1, 2, 3] -> [3, 5] -> [8] 이렇게 진행이 될텐데 중복으로 수가 더해지기 때문에 완전히 잘못된 생각임을 깨달았다.

 

다시 생각한 방법은 누적합을 이용하는 방법이었다. 5번재 수까지 더해진 값에서 2번째 수까지 더해진 값을 빼면 3번째부터 5번째까지 더한 값을 구할 수 있다는 생각에서 시작했다.

 

우선 펄스 수열[1, -1, 1, -1 ...]을 배열에 곱해줬다. 여기서 중요하다고 생각했던 점은 1로 시작하는 펄스 수열이 곱해지던 아니면 -1로 시작하는 수열이 곱해지던지 상관이 없다는 점이다. 답을 도출했을 때 최대값이나 최소값을 둘다 구해서 양수로 만들어 준 다음 비교하면 된다. 왜냐하면 최소값이 답이 되는 경우 음수인 경우일텐데 이 경우 펄스수열의 시작을 반대(1 또는 -1)로 했을 때 최대값이 답이 되는 경우이기 때문이다. 따라서 sequence 배열을 순회하면서 인덱스를 기준으로 짝수일 때 또는 홀수일 때를 구분하여 음수로 변환해줬다.

 

누적합을 새로운 배열에 넣고 출력해보니 문제의 예시로는 [-2, 1, 7, 8, 5, 4, 2, 6] 라는 값이 나왔다. 이를 보고 든 생각이 그냥 구한 누적합 배열에서 최대값에서 최소값을 빼면 항상 가장 최대가 되는 수가 나오지 않을까?라는 생각이 들었다. 문제의 예시를 예로 4번째 값까지 더한 값 8이 최대이고, 1번째까지 더한 -2가 최소값이다. 최대값 - 최소값 (8 - -2)를 하면 10이 나오는데 이때 2번째부터 4번째 값까지 더한 값이 나오게 되기 때문이다.

 

최소값과 최대값을 구하고 답을 구했는데 경우의 수가 3가지 있었다.

1. 둘 다 음수인 경우: 모두 음수인 경우로 최소값을 사용해서 답을 구한다.
2. 둘 다 양수인 경우: 모두 양수인 경우로 최대값을 사용해서 답을 구한다.
3. 부호가 서로 다른 경우: 음수 양수가 섞여있는 경우로 최대값과 최소값을 사용하여 답을 구한다.

1번째 경우일 때 최소값의 부호를 바꿔서 answer에 할당, 2번째 경우일 때  최대값을 할당, 마지막 3번째 경우일 때 양수로 변환하고 더해줬다.

 

⌨️ 코드

function solution(sequence) {
  var answer = 0;

  let sum = 0;
  let max = -Infinity;
  let min = Infinity;
  for (let i = 0; i < sequence.length; i++) {
    const s = i % 2 ? sequence[i] : -sequence[i];
    sum += s;

    if (max < sum) max = sum;
    if (min > sum) min = sum;
  }

  if (max > 0 && min > 0) answer = max;
  else if (max < 0 && min < 0) answer = -min;
  else answer = Math.abs(max) + Math.abs(min);

  return answer;
}