สมมติว่าเราได้รับอาร์เรย์ที่มีตัวเลขจำนวนเต็ม เราสามารถดำเนินการที่เราสามารถแทนที่ค่าของ array[i] ด้วยค่ากำลังสองของมัน หรือ array[i] * array[i] อนุญาตให้ดำเนินการประเภทนี้ได้เพียงครั้งเดียว และเราต้องส่งคืนผลรวมของอาร์เรย์ย่อยสูงสุดที่เป็นไปได้หลังการดำเนินการ ต้องระบุอาร์เรย์ย่อย
ดังนั้น หากอินพุตเป็นอาร์เรย์ =[4, 1, -2, -1] เอาต์พุตจะเป็น 17
หากเราแทนที่ค่าในอาร์เรย์[0] ด้วยค่ากำลังสอง อาร์เรย์จะกลายเป็น [16, 1, -2, -1] อาร์เรย์ย่อยสูงสุดที่เป็นไปได้จากนี้คือ [16, 1] และมีค่ารวมสูงสุด 16 + 1 =17
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- dp1 :=รายการใหม่ที่มีค่าลบอนันต์
- dp2 :=รายการใหม่ที่มีค่าลบอนันต์
- สำหรับแต่ละ num ในอาร์เรย์ ทำ
- แทรกสูงสุดของ ((องค์ประกอบสุดท้ายของ dp1 + num), num) ที่ส่วนท้ายของ dp1
- แทรกสูงสุดของ ((องค์ประกอบสุดท้ายที่สองของ dp1 + num^2), num^2, (องค์ประกอบสุดท้ายของ dp2 + num)) ที่ส่วนท้ายของ dp2
- คืนค่าองค์ประกอบสูงสุดของ 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
