<Lv.3> 연속 펄스 부분 수열의 합 (프로그래머스 : C#)

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

📕 문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들고자 한다.

펄스 수열 : 1, -1 번갈아 나오는 수열 (뭐가 앞에 오는지는 상관 x)

ex) 수열 [2, 3, -6, 1, 3, -1, 2, 4]
연속 부분 수열 [3, -6, 1] => [1, -1, 1] 곱하면 [3, 6, 1]로 변환됨 => 합이 가장 커짐

• Input
  정수 수열
• Output
  연속 펄스 부분 수열의 합 중 가장 큰 것

예제

풀이

간단한 dp 문제

dp[i, k] => i번째 원소까지 봤을 때 합의 최대 (k => 0, 1 => 양, 음)

dp[i,0] = Max(부호 대응하는 현재 값, 이전까지의 최대 합 + 자기 자신)

이때 이전까지의 최대 합은 k=1인 것을 가져와서 펄스를 유지해준다.

동일한 방식으로 dp [i,1]은 k=0인 dp를 가져와 펄스를 유지해준다.

using System;

public class Solution {
    public long solution(int[] sequence) {
        int n = sequence.Length;
        long[,] dp = new long[n,2]; 
        long max =0;
        
        // i, k => 0 = 양수 펄스, 1 = 음수 펄스 (i번째 원소)
        dp[0,0] = sequence[0];
        dp[0,1] = -1*sequence[0];
        max = Math.Max(dp[0,0],dp[0,1]);

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

        return max;
    }
}

결과