[JAVA/DP] 연속 펄스 부분 수열의 합

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의 원소는 정수입니다.

---

입출력 예sequenceresult

[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 = Long.MIN_VALUE;
        
        // 0번째 인덱스부터 
        // {1, -1, 1, -1 ...}이 곱해진 것과, 
        // {-1, 1, -1, 1 ...} 이 곱해진 걸 구하기
        long[] seqMinusDP = new long[sequence.length];
        long[] seqPlusDP = new long[sequence.length];
        
        int minusStart = -1;
        int plusStart = 1;
        
        for(int i=0; i<sequence.length; i++) {
            
            // i = 0 일 경우 초기화를 위해 그냥 저장
            if(i==0) {
                seqMinusDP[i] = sequence[i]*minusStart;
                seqPlusDP[i] = sequence[i]*plusStart;
            }
            // 아닐 경우 조건에 따라 실행
            else {
                // 이전 연산의 총합값과, 그냥 현재의 값을 비교해서 큰 값 넣기
                seqMinusDP[i] = Math.max(seqMinusDP[i-1] + sequence[i]*minusStart, sequence[i]*minusStart);
                seqPlusDP[i] = Math.max(seqPlusDP[i-1] + sequence[i]*plusStart, sequence[i]*plusStart);
            }
            
            // -1은 1로, 1은 -1로 변환
            minusStart *= -1;
            plusStart *= -1;
            
            // answer 저장
            answer = Math.max(answer, seqMinusDP[i]);
            answer = Math.max(answer, seqPlusDP[i]);
        }
        
        
        return answer;
    }
}