num이라는 배열이 있다고 가정합니다. 하위 배열 [nums_l, nums_l+1, ..., nums_r-1, nums_r]의 절대 합은 |nums_l + nums_l+1 + ... + nums_r-1 + nums_r|입니다. num의 모든 하위 배열의 최대 절대 합계를 찾아야 합니다(해당 하위 배열은 비어 있을 수 있음).
따라서 입력이 nums =[2,-4,-3,2,-6]과 같으면 하위 배열 [2,-4,-3,2]에 최대 절대 하위 배열 합계가 있기 때문에 출력은 11이 됩니다. 2 + (-4) + (-3) + 2| =11.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n:=숫자 크기
-
응답:=0, 온도:=0
-
범위 0에서 n - 1에 있는 i에 대해 수행
-
temp <0이면
-
온도:=0
-
-
temp:=온도 + 숫자[i]
-
ans:=ans 및 |temp|
의 최대값
-
-
온도:=0
-
범위 0에서 n - 1에 있는 i에 대해 수행
-
temp> 0이면
-
온도:=0
-
-
temp:=온도 + 숫자[i]
-
ans:=ans 및 |temp|
의 최대값
-
-
반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums):
n=len(nums)
ans=0
temp=0
for i in range(n):
if (temp<0):
temp=0
temp=temp+nums[i]
ans=max(ans,abs(temp))
temp=0
for i in range(n):
if (temp>0):
temp=0
temp=temp+nums[i]
ans=max(ans,abs(temp))
return ans
nums = [2,-4,-3,2,-6]
print(solve(nums)) 입력
[2,-4,-3,2,-6]
출력
11