[프로그래머스 C#] Lv.3 연속 펄스 부분 수열의 합

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

문제 이름 그대로 연속 펄스 부분 수열의 최대 합을 구하는 문제- 펄스 부분 수열이 적용된 경우에 따른 배열을 분리해 각 배열의 연속 부분 수열의 최대합을 구하면 됨

 

1) 펄스 부분 수열은 2가지 경우가 존재

- 인덱스를 기준으로 홀수에만 -1을 곱해준 경우와 짝수에만 -1을 곱해준 경우

 

2) 연속 부분 수열의 최대합을 구하는 방법

- 오른쪽 인덱스를 기준으로 하나씩 더해가며 음수가 되지 않는 경우라면 무조건 포함해야 함즉, dp로 간단하게 풀 수 있음 https://godgjwnsgur7.tistory.com/109

[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation

점화식 ( 코드상으로 dp = intArray, arr = sequence )

- dp[i] = Math.Max( 0, dp[i - 1] ) + arr[i] ( 단, i > 0 / dp[0] = arr[0] )

 

주석 참조

    using System;
    using System.Linq;

    public class Solution
    {
        public long solution(int[] sequence)
        {
            long answer = 0;
            var sequence2 = (int[])sequence.Clone();

            // 두 가지 펄스 수열을 곱한 배열
            for (int i = 0; i < sequence.Length; i++)
            {
                sequence[i] *= (i % 2 == 0) ? 1 : -1;
                sequence2[i] *= (i % 2 != 0) ? 1 : -1;
            }

            // 각 부분수열의 최대합을 구함
            long n1 = Function(sequence);
            long n2 = Function(sequence2);

            answer = Math.Max(n1, n2);

            return answer;
        }

        // 연속 부분수열의 최대합을 리턴하는 메서드
        public long Function(int[] sequence)
        {
            var intArray = new long[sequence.Length]; // dp배열

            intArray[0] = sequence[0];

            // i를 오른쪽 끝 인덱스로 하는 범위 내에서의 최대합
            for (int i = 1; i < intArray.Length; i++)
                intArray[i] = Math.Max(0, intArray[i - 1]) + sequence[i];

            return intArray.Max();
        }
    }