1744 - 수 묶기

묶거나(=다음 수와 곱하거나) / 묶지 않거나(=그냥 더하거나) 를 모두 해보면 된다.

큰 수는 큰수끼리 곱해지는 것이 항상 큰 값을 얻을 것이다.

배열 a를 비내림차로 정렬한 후, 모든 경우를 살핀다면 아래와 같이 표현할 수 있다.

$$f(pos) = max( a_{pos} + f(pos+1), a_{pos} \cdot a_{pos+1} + f(pos+2) )$$

여기에 메모이제이션을 적용하면 된다.