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

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

프로그래머스

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

연속 펄스 부분 수열의 최대 합을 구하는 문제

- 모든 부분수열에 대해 체크할 순 없으므로 최대 누적합을 구함 

 -> DP 알고리즘을 이용 // 음수가 될 경우 0으로 초기화하면서 연산

https://godgjwnsgur7.tistory.com/109

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

풀이 코드

using System;
using System.Linq;

public class Solution
{
    public long GetMaxAccValue(ref int[] intArray)
    {
        long[] dp = new long[intArray.Length];
        
        dp[0] = Math.Max(0, intArray[0]);
        for(int i = 1; i < dp.Length; i++)
            dp[i] = Math.Max(0, dp[i - 1]) + intArray[i];
        
        return dp.Max();
    }
    
    public long solution(int[] sequence)
    {
        int[] sequence2 = (int[])sequence.Clone();
        bool isCheck = false;
        
        for(int i = 0; i < sequence.Length; i++)
        {
            if(isCheck)
                sequence[i] *= -1;
            else
                sequence2[i] *= -1;
            
            isCheck = !isCheck;
        }
        
        return Math.Max(GetMaxAccValue(ref sequence), GetMaxAccValue(ref sequence2));
    }
}