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

 

🧫 문제 분석

✔️ 출처

연속 펄스 부분 수열의 합  level 3

📖 문제

 

문제를 잘못 이해해서 삽질했다.

 

펄스 수열을 연속 수열에 패턴대로 곱했을때 최댓값이 나오는 연속 펄수 부분수열을 구하는 것이였다.

 

나는 잘못 이해해서 펄스 수열 처럼 수열의 연속 부분수열이 3,-6,1,-4 이런식으로 1,-1 이런 패턴이 유지되는 연속 부분 수열에만 펄스 부분 수열 1,-1을 곱해서 양수가 되는 것만 합쳐서 최댓값을 구했다.

 

당연히 틀렸고 이 문제는 사실 펄스 수열은 페이크고 

누적합 문제이다. 

 

 주어진 수열에 

펄스 수열 패턴을 곱해서 2개의 수열로 만든다.

1,-1 패턴을 곱한 수열

-1, 1 패턴을 곱한 수열

 

이제 누적합으로 풀면 된다. 

 

나는 누적합 하면서 최댓값과 최솟값을 구하고 

 

최댓값 - 최솟값을 하되 최댓값 -최솟값 < 최댓값이 더 큰 경우가 있다.

 

-3 5 7 같은 경우 최댓값 9 최솟값 -3이다. 

이런 경우는 최솟값을 빼주면 12로 진짜 최댓값이 되고

 

5 6 7 같은 경우 최댓값 18, 최솟값 5

이 경우 빼게 되면 오히려 값이 줄어든다. 이때는 빼지 않고 최댓값만 반환한다. 

 

---

🔅 문제 풀이

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;

        long[] pulse1 = {1, -1};
        long[] pulse2 = {-1, 1};
        long min = Long.MAX_VALUE;
        long max = Long.MIN_VALUE;

        answer = Math.max(answer, calcPartSequenceSum(sequence, pulse1, min, max));
        answer = Math.max(answer, calcPartSequenceSum(sequence, pulse2, min, max));

        return answer;
    }

    private long calcPartSequenceSum(int[] sequence, long[] pulse, long min, long max) {
        long sum = 0;

        for (int i = 0; i < sequence.length; i++) {
            sum += sequence[i] * pulse[i % 2];
            min = Math.min(min, sum);
            max = Math.max(max, sum);
        }

        // min을 뺐을때와 안뺐을때 둘중 가장 큰 것을 고려
        if (max - min < max) {
            return max;
        }
        
        return max - min;
    }
}

 

❗ 오답노트 / 필요한 지식

1. 반성하게 된다. 정말..