[프로그래머스] LV3. 연속 펄스 부분 수열의 합

문제

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

---

입출력 예

sequence result

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

10

---

입출력 예 설명

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

풀이

사용 개념

카데인 알고리즘

연속 부분 배열의 최대 합을 구하는 효율적 방법으로 O(N) 시간 복잡도를 가지며 연속된 구간합 최대, 최소, 2차원 배열의 최대 구간합 등 응용 문제가 다양하다.

지금까지 최대 연속합 저장하면서, 현재 원소를 포함하는 새로운 연속합이 더 크면, 그걸로 바꾸는 방식이다.

int[] arr = {5, -2, 3, -1, 2};
int max = arr[0];
int current = arr[0];

for (int i = 1; i < arr.length; i++) {
    current = Math.max(arr[i], current + arr[i]);
    max = Math.max(max, current);
}

• current는 현재 연속된 부분의 최대값
• max = Math.max(max, current); 에서는 지금까지 봐온 current 중에서 최대값을 갱신

실제 풀이

풀이 단계

1. sequence 활용해서 [1, -1, 1, -1 …], [-1, 1, -1, 1 …] 해당하는 수열 만들기
2. 각각 수열에서 카데인 알고리즘 사용해서 최대 값 구하기
3. Math.max(a, b) 사용해서 각 수열 중 최대 값 도출

코드

import java.util.*;

class Solution {
    private static long kadane(int[] seq) {
        long max = seq[0];
        long curr = seq[0];
        
        for (int i = 1; i < seq.length; i++) {
            curr = Math.max(seq[i], curr + seq[i]);
            max = Math.max(max, curr);
        }
        
        return max;
    }
    
    public long solution(int[] sequence) {
        int[] seq1 = new int[sequence.length];
        int[] seq2 = new int[sequence.length];
        int x = 1;
        for (int i = 0; i < sequence.length; i++) {
            seq1[i] = sequence[i] * x;
            x *= -1;
            seq2[i] = sequence[i] * x;
        }

        long answer = Math.max(kadane(seq1), kadane(seq2));
        return answer;
    }
}

느낀점

카데인 알고리즘을 새로 알게되었다 나중에 활용해야지~