(JAVA/DP) 연속 펄스 하위 시퀀스의 합

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

프로그램 제작자

코드 중심 개발자를 고용하십시오. 배치 기반 위치 매칭. 프로그래머의 개발자별 프로필에 가입하고 기술 호환성이 좋은 회사와 연결하십시오.

Programmer.co.kr

연속 부분 펄스 시퀀스의 합

문제 설명

우리는 동일한 길이의 펄스 열로 기차의 연속적인 하위 열의 각 요소를 곱하여 연속적인 하위 펄스 열을 생성하려고 합니다. 펄스 열은 1 또는 -1로 시작하여 다음과 같이 1과 -1 사이를 번갈아가는 열입니다. 예: (1, -1, 1, -1 …) 또는 (-1, 1, -1, 1 …).
예를 들어 시퀀스 (2, 3, -6, 1, 3, -1, 2, 4)의 시퀀스 (3, -6, 1)이 시퀀스 (2, 3, -6)의 연속적인 서브 시퀀스라면 , 1, 4)에 펄스 열 (1, -1, 1)을 곱하면 열은 연속이고 부분 펄스 열은 (3, 6, 1)입니다. 또 다른 예로, 연속적인 하위 시퀀스(3, -1, 2, 4)와 펄스 시퀀스(-1, 1, -1, 1)를 곱하면 연속적인 펄스 하위 시퀀스(-3, -1, -2, 4)가 생성됩니다. .
정수 시퀀스 sequence가 매개변수로 지정된 경우 solve 함수를 완료하여 연속 펄스 하위 시퀀스의 최대 합을 반환합니다.

제한

1 ≤ 시퀀스 길이 ≤ 500,000
-100,000 ≤ 시퀀스의 요소 ≤ 100,000
- 시퀀스의 요소는 정수입니다.

I/O 예제 시퀀스 결과

(2, 3, -6, 1, 3, -1, 2, 4)

I/O 예시 설명

연속 서브 트레인(3, 6, 1)은 주어진 시퀀스의 연속 서브 트레인(3, -6, 1)에 임펄스 트레인(1, -1, 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;
    }
}