[leetcode] #1043. Partition Array for Maximum Sum

문제 설명

링크
배열요소의 합이 최대가 되도록 최대 길이k 로 배열을 분할하는 문제
분할된 각 부분 배열들은 모두 최대값으로 대치됨

ex. [1, 15, 7, 9, 2, 5, 10] => [15, 15, 15, 9, 10,10, 10]

접근 - DP

• 최대 길이가 k 이므로 현재 요소(i) 에서 i-1 ~ i-k 까지 상태를 비교해야 함
• (j = i ~ k) dp[i] = max(dp[i-j] + max(A[i-1], ..., A[i-j]) * j)

코드 1

• discussion 안보고 혼자 짜 본 코드

if len(arr) < k:
   return max(arr) * len(arr)
        
dp = [0] * len(arr)
        
for i in range(len(arr)):
    if i < k:
         dp[i] = max(arr[:i + 1]) * (i + 1)
    else:
         caseArr = [dp[i-step] + max(arr[i-step + 1 : i + 1]) * step for step in range(1, k + 1)]
         dp[i] = max(caseArr)
      
return dp[-1]

• 1 ~ k 까지 계속 최대값을 찾고, 반복문을 돌아서 시간 효율이 좋지 못한 편

코드 2

• discussion 코드
• [0, n-1] 이 아닌 [1, n] 으로 바꿔서 코딩

N = len(arr)
dp = [0] * (N + 1)
for i in range(1, N + 1):
     curMax = 0
     for s in range(1, min(k, i) + 1):
         curMax = max(curMax, arr[i - s])
         dp[i] = max(dp[i], dp[i - s] + curMax * s)

return dp[N]

• 최대값을 매번 갱신하는 방식
• min(k, i) 때문에 헷갈리고 난 이렇게 생각해 낼 수 없을 것 같음

코드 3

• 코드 2 를 바탕으로 0 ~ n-1 의 배열을 가지고 구할 수 있도록 구현해봄

N = len(arr)
dp = [0] * N
dp[0] = arr[0]
for i in range(N):
    if i < k:
        dp[i] = max(arr[:i + 1]) * (i + 1)
        continue
    curMax = arr[i]
    for s in range(1, k + 1):
         curMax = max(curMax, arr[i - s + 1])
         dp[i] = max(dp[i], dp[i - s] + curMax * s)

return dp[-1]