สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums เราต้องหาผลรวมสัมบูรณ์ของอาร์เรย์ย่อย [nums_l, nums_l+1, ..., nums_r-1, nums_r] คือ |nums_l + nums_l+1 + ... + nums_r-1 + nums_r| เราต้องหาผลรวมสัมบูรณ์สูงสุดของอาร์เรย์ย่อยของ nums ใดๆ (อาร์เรย์ย่อยนั้นอาจว่างเปล่าได้)
ดังนั้น ถ้าอินพุตเท่ากับ nums =[2,-4,-3,2,-6] เอาต์พุตจะเป็น 11 เนื่องจากอาร์เรย์ย่อย [2,-4,-3,2] มีผลรวมของ subarray สัมบูรณ์สูงสุด | 2 + (-4) + (-3) + 2| =11.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n:=ขนาดของ nums
-
ตอบ:=0, อุณหภูมิ:=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ
-
ถ้าอุณหภูมิ <0 แล้ว
-
อุณหภูมิ:=0
-
-
temp:=temp + nums[i]
-
ans:=สูงสุดของ ans และ |temp|
-
-
อุณหภูมิ:=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ
-
ถ้าอุณหภูมิ> 0 แล้ว
-
อุณหภูมิ:=0
-
-
temp:=temp + nums[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
