[프로그래머스] 연속 펄스 부분 수열의 합 - C++

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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의 원소는 정수입니다.

---

입출력 예sequenceresult

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

10

---

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

---

 

N이 50만이다 N^2으로 풀 수 없다.

연속합을 활용하여 O(N)으로 풀 수 있다.

다만 펄스 배열을 곱해주어야 하기 때문에 기존 배열을 변환해야 하므로 홀수 번째마다 -1을 곱한다.

이 곱한 배열을 더해 나가면서 연속합을 구하고

이 곱한 배열을 빼 나가면서 연속합을 구한 다음 최댓값을 비교하여 답을 얻어 낼 수 있다. 

왜냐하면

[a, b, c] 배열을 [a,-b, c]로 바꾼 뒤 더하면 a - b + c 가 되어 펄스 배열 [1,-1,1]을 곱한 것이 되고 빼면 -a +b -c 가 되어 [-1,1,-1]을 곱한 것이 되기 때문이다.

 

---

문제를 보고 LIS 를 활용한 DP인줄 알았지만 해당 알고리즘은 N^2의 공간과 시간이 필요한다 N이 너무 컸다. 고민을 더 해봤지만 공간 복잡도와 시간 복잡도가 낮은 알고리즘이 생각이 나지 않았다. 연속합이라는 어디서 들어본 키워드로 검색을 했더니 해당 방법으로 쉽게 구할 수 있을 것 같았다. 알고리즘만 가져와서 적용을 시키니 쉽게 풀렸다. 

다만 중간에 매크로 #define 과 관련해서 굉장히 애를 먹었다.

#define max(a,b) a > b ? a : b 로 설정을 하였다.

long long 이 문제인 줄 알았는데 알고 보니 max(a,b) + arr[i]; 를 해버려서 a : b + arr[i] 가 되버렸던 것이었다. max를 저런 식으로 종종 사용했는데 이렇게 식 중간에 쓴적이 없었나보다. 좋은거 하나 배웠다!