[Algorithm] 연속 펄스 부분 수열의 합

[hwangJi-dev]

💬 문제

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

💬 Idea

• DP를 이용하여 수열의 합의 Max값을 채워나간다.

• sequence와 -1로 시작하는 (-1, 1, -1, 1, -1, 1, …) 의 배열을 곱한 배열을 s1에 저장하고,

• sequence와 1로 시작하는 (1,-1, 1, -1, 1, -1, …) 의 배열을 곱한 배열을 s2에 저장한다.

• [ dp 점화식 ]

  • (dp에 저장된 j - 1값 + 현재 s1의 값) 과 (s1에 저장된 j - 1값 + 현재 s1의 값) 중 더 큰 값을 dp[j]에 저장한다.
  • ⇒ dp1[j] = max(dp1[j - 1] + s1[j], s1[j - 1] + s1[j])

• dp1에 저장된 max값과 dp2에 저장된 max값 중 더 큰 값을 리턴한다.

💬 풀이

import Foundation

func solution(_ sequence:[Int]) -> Int64 {
 var s1: [Int] = []
 var s2: [Int] = []
 var purse = (-1, 1)
 
 for i in 0..<sequence.count {
 s1.append(sequence[i] * purse.0)
 s2.append(sequence[i] * purse.1)
 purse = (purse.0 * -1, purse.1 * -1)
 }
 
 var dp1 = Array(repeating: 0, count: s1.count)
 var dp2 = Array(repeating: 0, count: s2.count) 
 dp1[0] = s1[0]
 dp2[0] = s2[0]
 
 for j in 1..<dp1.count {
 dp1[j] = max(dp1[j - 1] + s1[j], s1[j - 1] + s1[j])
 dp2[j] = max(dp2[j - 1] + s2[j], s2[j - 1] + s2[j])
 }
 
 return Int64(max(dp1.max()!, dp2.max()!))
}