Chương trình tìm tổng tuyệt đối tối đa của bất kỳ mảng con nào trong Python

Giả sử chúng ta có một mảng được gọi là nums. Chúng ta phải tìm tổng tuyệt đối của một mảng con [nums_l, nums_l + 1, ..., nums_r-1, nums_r] là | nums_l + nums_l + 1 + ... + nums_r-1 + nums_r |. Chúng ta phải tìm tổng tuyệt đối lớn nhất của bất kỳ dãy con nào gồm nums (mảng con đó có thể trống).

Vì vậy, nếu đầu vào giống như nums =[2, -4, -3,2, -6], thì đầu ra sẽ là 11 vì mảng con [2, -4, -3,2] có tổng mảng con tuyệt đối lớn nhất | 2 + (-4) + (-3) + 2 | =11.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums

• ans:=0, temp:=0

• đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện

  • nếu nhiệt độ <0, thì

    • tạm thời:=0

  • temp:=temp + nums [i]

  • ans:=tối đa ans và | temp |

• tạm thời:=0

• đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện

  • nếu nhiệt độ> 0, thì

    • tạm thời:=0

  • temp:=temp + nums [i]

  • ans:=tối đa ans và | temp |

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[2,-4,-3,2,-6]

Đầu ra

11