https://school.programmers.co.kr/learn/courses/30/lessons/161988

---

문제 설명

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

---

풀이

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        long op =1;
        long[] dp1 = new long[sequence.length+1];
        long[] dp2 = new long[sequence.length+1];
        for(int i=0; i<sequence.length; i++){
            long temp1 = sequence[i]*op;
            op *= -1;
            long temp2 =sequence[i]*op;
            
            dp1[i+1] = Math.max(dp1[i]+temp1, temp1);
            dp2[i+1] = Math.max(dp2[i]+temp2, temp2);
            answer = Math.max(answer, Math.max(dp1[i+1], dp2[i+1]));
        }
        return answer;
    }
}

sequence의 길이가 최대 100000만이기 때문에 O(n^2)하면 안된다. 즉 부분 수열의 길이를 1부터 100000까지 늘려 슬라이딩윈도우 하면 안된다는 뜻.

그래서 최대한 O(n)으로 시도했을 때 처음 생각한 풀이가 양수가 있는 부분 수열만 더하기 였음. (음수만 없으면 된다는 그리디한 생각)
그러나 3, 1,10000같은 수열이 있을 때 최대값은 10002가 됨 (-3,1,-10000) (3,-1,10000)

그러니 DP로 풀이해 냄.

---

결과