สมมติว่าเรามีอาร์เรย์ชื่อ target ที่มีค่าบวก ตอนนี้พิจารณาอาร์เรย์ initial ขนาดเดียวกันเติมศูนย์ทั้งหมด เราต้องหาจำนวนการดำเนินการน้อยที่สุดที่จำเป็นเพื่อสร้างอาร์เรย์ target จาก initial หากเราทำการดำเนินการนี้: (เลือกซับอาร์เรย์ใดก็ได้จาก initial และเพิ่มค่าแต่ละตัวขึ้น 1)
เช่น ถ้าอินพุตคือ target = [2,3,4,3,2] ผลลัพธ์จะเป็น 4 เพราะเริ่มต้นอาร์เรย์คือ [0,0,0,0,0] รอบแรกเลือกซับอาร์เรย์ดัชนี 0 ถึง 4 เพิ่ม 1 กลายเป็น [1,1,1,1,1] รอบที่สองเลือก 0 ถึง 4 อีกครั้ง กลายเป็น [2,2,2,2,2] แล้วเลือกดัชนี 1 ถึง 3 เพิ่ม กลายเป็น [2,3,3,3,2] สุดท้ายเลือกดัชนี 2 ทำให้ได้ [2,3,4,3,2] เท่ากับ target
วิธีแก้ปัญหา
- prev_num := 0
- steps := 0
- สำหรับแต่ละ val ใน target:
- steps := steps + val - prev_num ถ้า val > prev_num มิฉะนั้น 0
- prev_num := val
- return steps
ตัวอย่าง
def solve(target):
prev_num = 0
steps = 0
for val in target:
steps += val - prev_num if val > prev_num else 0
prev_num = val
return steps
target = [2,3,4,3,2]
print(solve(target))
อินพุต
[2,3,4,3,2]
เอาต์พุต
4
