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

https://school.programmers.co.kr/learn/courses/30/lessons/161988?language=java

완전탐색으로 풀기엔 Sequence의 길이가 50000이었고 결국 12번부터 시간초과 또는 런타임 에러가 발생했다.

펄스 부분의 수열 합이 절대 0보다 작아질 수 없다는 것이 키포인트였고

펄스 부분의 수열 합이 0보다 작아질 때 0으로 처리하고 나아가는 방식을 취했다.

import java.util.*;
class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        long s1 = 0;
        long s2 = 0;
        int pivot = 1;
        for (int num : sequence) {
            s1 += pivot * num;
            s2 += (-pivot)* num;
            s1 = Math.max(0,s1);
            s2 = Math.max(0,s2);
            answer = Math.max(answer,Math.max(s1,s2));
            pivot *= -1;
        }
        return answer;
    }
    // 0이하로 떨어질 수 없다.
}

 

간단한 아이디어의 문제였고 마치 배열의 최댓값을 구한 문제같은 기본적인 dp문제 였던 것 같다.