(알고리즘) 연속 부분 펄스 시퀀스의 합

by

문제

우리는 동일한 길이의 펄스 열로 기차의 연속적인 하위 열의 각 요소를 곱하여 연속적인 하위 펄스 열을 생성하려고 합니다.

펄스 열은 1 또는 -1로 시작하여 다음과 같이 1과 -1 사이를 번갈아가는 열입니다.

예: (1, -1, 1, -1 …) 또는 (-1, 1, -1, 1 …).
예를 들어 시퀀스 (2, 3, -6, 1, 3, -1, 2, 4)의 시퀀스 (3, -6, 1)이 시퀀스 (2, 3, -6)의 연속적인 서브 시퀀스라면 , 1, 4)에 펄스 열 (1, -1, 1)을 곱하면 열은 연속이고 부분 펄스 열은 (3, 6, 1)입니다.

또 다른 예로, 연속적인 하위 시퀀스(3, -1, 2, 4)와 펄스 시퀀스(-1, 1, -1, 1)를 곱하면 연속적인 펄스 하위 시퀀스(-3, -1, -2, 4)가 생성됩니다.

.
정수 시퀀스가 ​​매개변수로 제공된 경우 solve 함수를 완료하여 연속 펄스 하위 시퀀스의 최대 합을 반환합니다.

제한

  • 1 ≤ 시퀀스 길이 ≤ 500,000
  • -100,000 ≤ 시퀀스의 요소 ≤ 100,000
    • 시퀀스의 요소는 정수입니다.

I/O 예시

(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) 최대값이 답이 되기 때문입니다.

따라서 시퀀스 배열을 통해 반복할 때 인덱스를 기준으로 짝수인지 홀수인지 구분하여 음수로 변환하였다.

누적 합계를 새로운 배열에 넣고 출력하면 문제의 예가 (-2, 1, 7, 8, 5, 4, 2, 6)으로 나옵니다.

이거 보고 든 생각은 그냥 저장 누적합 배열의 최대값에서 최소값을 빼면 항상 가장 큰 수가 나오지 않나요?나는 생각했다.

문제의 예로 4번째 값에 8을 더한 값이 최대값이고 1번째 값에 -2를 더한 값이 최소값입니다.

최대값-최소값(8–2)을 하면 10이 나오는데 그때 2~4번째 값의 합이 나오기 때문이다.

최소값과 최대값을 찾아 답을 얻었지만 3가지 경우가 있었다.

  1. 둘 다 음수인 경우: 둘 다 음수인 경우 최소값을 사용하여 답을 찾습니다.

  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;
}

Related Posts: