문제 링크

문제 풀이 아이디어

부분합

N이 최대 500,000입니다. O(N)의 시간복잡도를 가진 알고리즘을 사용해야 합니다. 연속된 부분 수열의 합 문제는 부분합을 사용할 경우 O(N)의 시간복잡도로 문제를 해결할 수 있습니다.

펄스 수열

다만 이 문제는 단순한 부분합을 사용할 수 없도록 펄스 수열이라는 개념을 도입했습니다. 따라서 부분합을 2개로 나누어서 계산을 해야 합니다.

따라서 부분합을 구할 때 마지막 펄스가 1인 경우, 마지막이 -1이었던 부분수열의 합에 마지막 원소에 *1을 해서 더하고, 마지막 펄스가 -1인 경우 마지막이 1이었던 부분수열의 합에 -1을 곱한 마지막 원소를 더하면 됩니다.

부분수열의 합의 최댓값

i번째 원소를 마지막으로 하는 부분수열의 합의 최댓값은 (i까지의 모든 부분 수열의 합)에서 (i - 1까지의 부분 수열의 합 중에서 최솟값)을 빼주면 됩니다.

주의할 점은 계산할 때 사용하는 두 개의 부분 수열은 같은 펄스 수열을 곱한 수열이어야 합니다. 따라서 1부터 곱하기 시작한 부분합과 -1부터 곱하기 시작한 부분합을 분리해서 최솟값을 갱신해나가야 합니다.

코드

func solution(_ sequence:[Int]) -> Int64 {
    
    var ans = Int.min
    // 현재 곱하는 pulse를 정의
    var pulse = 1
    // sum1: 1부터 곱한 부분합
    // sum2: -1부터 곱한 부분합
    // min1: 1부터 곱한 부분합 중에 (i - 1)까지의 최솟값
    // min2: -1부터 곱한 부분합 중에 (i - 1)까지의 최솟값
    var sum1 = 0, sum2 = 0, min1 = 0, min2 = 0
    
    for i in 0..<sequence.count {
        
        // 현재 pulse를 곱해서 부분합 구하기
        sum1 += sequence[i] * pulse
        sum2 += sequence[i] * -pulse
        
        // 부분합의 최댓값 갱신
        // (i를 마지막으로 하는 부분수열합의 최댓값) = (i까지의 누적합) - ((i - 1)까지의 누적합 중에 최소값)
        ans = max(sum1 - min1, sum2 - min2, ans)
        
        // (i + 1)의 최댓값 구하기 전에 i까지의 최솟값 갱신
        min1 = min(sum1, min1)
        min2 = min(sum2, min2)
        
        // 원소 바뀔 때 pulse의 부호도 바꾸어 주기
        pulse *= -1
    }
    
    return Int64(ans)
}