정수를 포함하는 배열이 주어진다고 가정합니다. array[i] 값을 제곱 값으로 바꿀 수 있는 작업을 수행할 수 있습니다. 또는 배열[i] * 배열[i]. 이러한 종류의 작업은 하나만 허용되며 작업 후 가능한 최대 하위 배열의 합계를 반환해야 합니다. 하위 배열은 비워둘 수 없습니다.
따라서 입력이 array =[4, 1, -2, -1]과 같으면 출력은 17이 됩니다.
array[0]의 값을 제곱 값으로 바꾸면 배열은 [16, 1, -2, -1]이 됩니다. 이로부터 가능한 최대 부분배열은 [16, 1]이며, 최대합값은 16 + 1 =17입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- dp1 :=음의 무한대 값을 포함하는 새 목록
- dp2 :=음의 무한대 값을 포함하는 새 목록
- 배열의 각 숫자에 대해 다음을 수행합니다.
- dp1의 끝에 ((dp1의 마지막 요소 + num), num)의 최대값 삽입
- dp2의 끝에 ((dp1의 두 번째 마지막 요소 + num^2), num^2, (dp2의 마지막 요소 + num))의 최대값 삽입
- dp2의 최대 요소를 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(array):
dp1 = [float('-inf')]
dp2 = [float('-inf')]
for num in array:
dp1.append(max(dp1[-1] + num, num))
dp2.append(max(dp1[-2] + num**2, num**2, dp2[-1]+num))
return max(dp2)
print(solve([4, 1, -2, -1])) 입력
[4, 1, -2, -1]
출력
17