n개의 정수 'nums' 배열이 있다고 가정합니다. 'nums'의 각 값은 '힘'을 나타냅니다. 배열의 길이가 2보다 크고 배열의 첫 번째 값과 마지막 값이 같은 경우 배열은 '유효한' 것으로 평가됩니다. 나머지 요소가 조건을 만족할 수 있도록 배열에서 요소를 삭제하여 배열을 유효하게 만들어야 합니다. 출력으로 어레이의 모든 거듭제곱 값을 더하여 어레이의 가능한 최대 거듭제곱 값을 반환합니다.
따라서 입력이 nums =[3, 4, 5, 3, 4]와 같으면 출력은 16이 됩니다.
배열 nums에서 첫 번째 값 3을 제거하면 [4, 5, 3, 4]가 됩니다. 이것은 유효한 배열이고 거듭제곱의 합은 4 + 5 + 3 + 4 =16입니다. 이것은 주어진 입력에서 유효한 배열에 대해 가능한 최대 합입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
테이블 :=새 지도
-
접두사 :=값 0으로 초기화된 새 목록
-
음수 :=값 0으로 초기화된 새 목록
-
숫자로 된 각 인덱스 i와 값 j에 대해 수행
-
j가 테이블에 없으면
-
table[j] :=새로운 쌍 (i, 0)
-
그렇지 않으면
-
테이블[j, -1] :=i
-
-
접두사 + j의 마지막 요소와 동일한 접두사에 새 요소 추가
-
네거티브의 마지막 요소 복제
-
j <0이면
-
음수 마지막 요소 :=음수 마지막 요소 + j
-
-
-
-
ans :=음의 무한대
-
테이블의 모든 값에서 각 쌍(i,j)에 대해 수행
-
j가 0과 같지 않으면
-
sm1 :=접두사[j+1] - 접두사[i]
-
j> i+1이면
-
sm2 :=음수[j] - 음수[i+1]
-
-
그렇지 않으면
-
sm2 :=0
-
-
ans :=최대 (ans, sm1 - sm2)
-
-
-
반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums):
table = {}
prefix = [0]
negative = [0]
for i, j in enumerate(nums):
if j not in table:
table[j] = [i, 0]
else:
table[j][-1] = i
prefix += prefix[-1] + j,
negative += negative[-1],
if j < 0:
negative[-1] += j
ans = float('-inf')
for i,j in table.values():
if j != 0:
sm1 = prefix[j+1] - prefix[i]
sm2 = negative[j] - negative[i+1] if j > i+1 else 0
ans = max(ans, sm1 - sm2)
return ans
print(solve([3, 4, 5, 3, 4])) 입력
[3, 4, 5, 3, 4]
출력
16