โปรแกรมหาผลรวมสัมบูรณ์สูงสุดของย่อยอาร์เรย์ใน Python

ปัญหา

มีอาร์เรย์ nums หาผลรวมสัมบูรณ์สูงสุดของย่อยอาร์เรย์ใดๆ (รวมถึงย่อยอาร์เรย์ว่าง) คือ |sum|

ตัวอย่าง

nums = [2,-4,-3,2,-6] → ผลลัพธ์ 11 เพราะย่อยอาร์เรย์ [2,-4,-3,2] ให้ |2-4-3+2| = 11

ขั้นตอนการแก้ปัญหา

1. n := len(nums), ans := 0, temp := 0
2. วนลูป i จาก 0 ถึง n-1 (หาผลรวมบวกสูงสุด):
   • ถ้า temp < 0: temp := 0
   • temp += nums[i]
   • ans := max(ans, abs(temp))
3. temp := 0
4. วนลูป i จาก 0 ถึง n-1 (หาผลรวมลบสูงสุด):
   • ถ้า temp > 0: temp := 0
   • temp += nums[i]
   • ans := max(ans, abs(temp))
5. คืน ans

การนำไปใช้งาน (Python)

def solve(nums):
    n = len(nums)
    ans = 0
    temp = 0
    for i in range(n):
        if temp < 0:
            temp = 0
        temp += nums[i]
        ans = max(ans, abs(temp))
    temp = 0
    for i in range(n):
        if temp > 0:
            temp = 0
        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