[프로그래머스]LV 3 연속 펄스 부분 수열의 합

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

프로그래머스

 

접근 방법

1. 최대 50만 길이의 배열이 input으로 들어온다. 즉 O(nlogn) 이하의 알고리즘이 가능하다
2. 입력 배열에 각각 [1,-1,1,-1 ,1,-1...] [-1,1 -1,1, -1,1...]을 곱한 두가지 케이스에서 최대 부분수열의 max값을 찾아야한다
3. 따라서 dp 배열에  0번 열에는 +값만, 1번 열에는 -값을 저장한다
4. 즉, (i,0) 에는 (i-1,1) + seq[i]값이 0보다 크면 들어온다. (i,1) 에는 (i-1,0) - seq[i]값이 0보다 크면 들어온다

코드

class Solution {
    public long solution(int[] sequence) {
        int n = sequence.length;
        long[][] dp = new long[n][2];
        
        dp[0][0] = sequence[0];
        dp[0][1] = -sequence[0];
        
        for(int i = 1 ; i < n ; 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];
        }
        
        long ans = 0L;
        for(long[] d: dp) ans = Math.max(ans, Math.max(d[0], d[1]));
        
        return ans;
    }
}