프로그래머스 - 연속 펄스 부분 수열의 합 - DP - Java

1. 문제

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

2. 풀이

참고 풀이

처음에는 DP라는 생각을 하지 못했다. DP는 작은 부분의 합을 이용한다는 점을 항상 염두해주자!

3. 전체코드

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        boolean isPulse = true;
        
        long pulse1 = 0;
        long pulse2 = 0;
        
        for(int num : sequence){
            
            pulse1 += isPulse ? num : -num;
            pulse2 += isPulse ? -num : num;
            
            pulse1 = Math.max(0, pulse1);
            pulse2 = Math.max(0, pulse2);
            
            answer = Math.max(answer, Math.max(pulse1, pulse2));
            
            isPulse = !isPulse;
        }
        return answer;
    }
}