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

ได้รับอาร์เรย์ตัวเลข สามารถทำการดำเนินการได้ครั้งเดียว: เลือก array[i] แทนที่ด้วย array[i]^2 ต้องหาผลรวมซับอาร์เรย์สูงสุดที่เป็นไปได้ (ซับอาร์เรย์ไม่ว่าง)

ตัวอย่าง: array = [4,1,-2,-1] ผลลัพธ์ 17 (ยกกำลังสอง 4→16 ซับอาร์เรย์ [16,1] ผลรวม 17)

วิธีแก้ปัญหา (Dynamic Programming)

1. dp1 := [-inf] (max subarray sum ปกติจนถึง i)
2. dp2 := [-inf] (max subarray sum ที่ใช้การยกกำลังสองแล้วจนถึง i)
3. วน num ใน array:
   • dp1.append(max(dp1[-1]+num, num))
   • dp2.append(max(dp1[-2]+num^2, num^2, dp2[-1]+num))
4. คืน max(dp2)

ตัวอย่างโค้ด

def solve(array):
    dp1 = [float('-inf')]
    dp2 = [float('-inf')]
    for num in array:
        dp1.append(max(dp1[-1] + num, num))
        dp2.append(max(dp1[-2] + num**2, num**2, dp2[-1] + num))
    return max(dp2)

print(solve([4,1,-2,-1]))

อินพุต

[4,1,-2,-1]

เอาต์พุต

17