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

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

1. DP 점화식 세우기

 

어떤 수를 사용했는가는 관심사가 아니므로, i번째에 이룰 수 있는 최댓값만 기록

 

dp[i][0] = i번째가 1 *  sequence[i]일 때 이룰 수 있는 최댓 값
dp[i][1] = i번째가 -1 * sequence[i]일 때 이룰 수 있는 최댓 값

 

2. 최댓 값 산정 방식

 

dp[i][0] = Math.max(dp[i-1][1], 0) + sequence[i];
dp[i][1] = Math.max(dp[i-1][0], 0) - sequence[i];

 

i-1 이 음수라면 i번 째 값을 낮추기만 하므로 최댓 값 해에 포함하지 않는다.

 

3. 출력

 

dp[dp.length()-1]이 아닌, dp[0~ dp.length()-2]에 해당하는 부분 수열이 정답일 수 있으므로 for each문으로 정답 도출

 

4. 고려 사항

문제에서, sequence는 5만 이하

원소 값은 -10만 이상 10만 이하

 

최대 (5만/2 * 10만) - (5만/2 *-10만) = 50억 이므로 long 사용

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

        long dp[][] = new long[sl][2];

        dp[0][0] = sequence[0];
        dp[0][1] = -sequence[0];

        for(int i=1; i<sl; i++) {
            dp[i][0] = Math.max(dp[i-1][1], 0) + sequence[i];
            dp[i][1] = Math.max(dp[i-1][0], 0) - sequence[i];
        }

        for(long[] col : dp)
            answer = Math.max(answer, Math.max(col[0], col[1]));

        return answer;
    }
}