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

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

 

문제 접근

이번 문제도 DP를 사용해서 푼다. 

 

DP에 대한 간단한 설명이 필요하신 분은 밑에 링크에서 참고해 주세요

https://20240228.tistory.com/51

[Java] 프로그래머스 level3 가장 긴 팰린드롬

 

문제의 핵심은 연속 부분 수열이라는 점이다 

 

입출력 예를 보자. 

[2, 3, -6, 1, 3, -1, 2, 4]         result : 10 

 

연속 부분 수열 [3, -6, 1] 에 [1, -1, 1] 을 곱하여 [3, 6, 1] 을 얻고 합은 10이다.

 

1번 case 펄스 수열이 -1로 시작 

[-2, 3, 6, 1, -3, -1, -2 ,4]

 

2번 case 펄스 수열이 1로 시작 

[2,-3, -6, -1, 3, 1, 2, -4]

 

이렇게 2가지 case가 있을 때는 2차원 배열 DP를 사용하고 배열의 열을 case로 지정한다.

DP[k][0] = 1번 case에서 k번째 원소를 포함하는 가장 큰 연속 부분 수열 누적합 

DP[k][1] = 2번 case에서 k번째 원소를 포함하는 가장 큰 연속 부분 수열 누적합 

 

간단하게 1번 case로 설명하겠다.

 

DP[1][0] = -2 

 

DP[2][0] = ??  처음 점화식을 세울 때 2번째 원소를 포함하는 가장 큰 연속 부분 수열 누적합이라고 설명을 했다. 

근데 전 원소인 -2를 포함하게 되면 -2 + 3 = 1로 그냥 2번째 원소로 시작하는 누적합보다 적다. 

DP[2][0] = 3이다. 

 

DP[3][0] = ?   DP[3][0] = Math.max(DP[3][0], DP[3-1][0] + DP[3][0]) 이다.  DP[3][0] = 9

 

이제 끝났다 우리는  DP[k][0] = Math.max(DP[k][0], DP[k-1][0] + DP[k][0]) 공식을 통해서 새로운 부분 수열을 시작할지 

말지 결정하면 된다. 

 

이걸 for문 1개로 정리해서 풀면 밑에 코드가 나온다 

정답 코드

import java.util.*;
class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        int size = sequence.length;
        
        long [][] DP = new long [size+1][2];
        
        for(int i = 1; i <= size; i++){
            int target = sequence[i-1];
           
            if(i % 2 == 1){
                DP[i][0] = target;
                DP[i][1] = target * -1;
            }
            else{
                DP[i][0] = target * -1;
                DP[i][1] = target;
            }
            if(DP[i][1] < DP[i-1][1] + DP[i][1]) {
                DP[i][1] += DP[i-1][1];
            }
            
            if(DP[i][0] < DP[i-1][0] + DP[i][0]) {
                DP[i][0] += DP[i-1][0];
            }
            
            answer = Math.max(answer , Math.max(DP[i][1], DP[i][0]));
        }      
        return answer;
    }
}