dp[i] = sum이 i인 2개 이상의 positive integers의 max product
_sum을 2 ~ n까지 돌면서, two pointer left = 1, right = _sum - 1을 양끝에서부터 좁혀나가며 dp[_sum]을 max product 값으로 업데이트 한다.
for _sum in range(2, n + 1):
left, right = 1, _sum - 1
# left와 right를 중앙으로 이동해가며 dp[_sum] 업데이트
while left <= right:
dp[_sum] = max(dp[_sum], max(left, dp[left]) * max(right, dp[right]))
left += 1
right -= 1
Approach
다음과 같이 dp table을 구성한다.
_sum을2~n까지 돌면서, two pointerleft = 1,right = _sum - 1을 양끝에서부터 좁혀나가며dp[_sum]을 max product 값으로 업데이트 한다.Complexity
O(n^2)O(n)