โปรแกรมหาค่าสูงสุดของอาร์เรย์ 'ที่ถูกต้อง' ใน Python

สมมุติว่าเรามี 'nums' จำนวนเต็ม n ตัว แต่ละค่าใน 'nums' แสดงถึง 'กำลัง' อาร์เรย์จะได้รับการประเมินว่า 'ถูกต้อง' หากความยาวของอาร์เรย์มากกว่าสอง และค่าแรกและค่าสุดท้ายของอาร์เรย์เท่ากัน เราต้องทำให้อาร์เรย์ถูกต้องโดยการลบองค์ประกอบออกจากอาร์เรย์เพื่อให้ส่วนที่เหลือสามารถตอบสนองเงื่อนไขได้ เมื่อเป็นเอาต์พุต เราจะคืนค่ากำลังสูงสุดที่เป็นไปได้ของอาร์เรย์โดยการเพิ่มค่ากำลังทั้งหมดของอาร์เรย์

ดังนั้น หากอินพุตเป็น nums =[3, 4, 5, 3, 4] เอาต์พุตจะเป็น 16

หากเราลบค่าแรก 3 ออกจากจำนวนอาร์เรย์ ค่านั้นจะกลายเป็น [4, 5, 3, 4] นี่คืออาร์เรย์ที่ถูกต้อง และผลรวมของกำลังคือ 4 + 5 + 3 + 4 =16 ซึ่งเป็นผลรวมสูงสุดที่เป็นไปได้สำหรับอาร์เรย์ที่ถูกต้องจากอินพุตที่กำหนด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• table :=แผนที่ใหม่

• คำนำหน้า :=รายการใหม่ที่เริ่มต้นด้วยค่า 0

• ค่าลบ :=รายการใหม่ที่เริ่มต้นด้วยค่า 0

• สำหรับแต่ละดัชนี i และค่า j เป็น nums ทำ

  • ถ้า j ไม่มีอยู่ในตารางแล้ว

    • table[j] :=คู่ใหม่ (i, 0)

    • มิฉะนั้น

      • ตาราง[j, -1] :=ฉัน

    • เพิ่มองค์ประกอบใหม่ให้กับคำนำหน้าซึ่งเท่ากับองค์ประกอบสุดท้ายของคำนำหน้า + j

    • ทำซ้ำองค์ประกอบสุดท้ายของค่าลบ

    • ถ้า j <0 แล้ว

      • องค์ประกอบสุดท้ายของค่าลบ :=องค์ประกอบสุดท้ายของค่าลบ + j

• ans :=ลบอินฟินิตี้

• สำหรับแต่ละคู่ (i,j) ในทุกค่าของตาราง ทำ

  • ถ้า j ไม่เหมือนกับ 0 แล้ว

    • sm1 :=คำนำหน้า[j+1] - คำนำหน้า[i]

    • ถ้า j> i+1 แล้ว

      • sm2 :=ลบ[j] - ลบ[i+1]

    • มิฉะนั้น

      • sm2 :=0

    • ans :=สูงสุดของ (ans, sm1 - sm2)

• กลับมาอีกครั้ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(nums):
   table = {}
   prefix = [0]
   negative = [0]
   for i, j in enumerate(nums):
      if j not in table:
         table[j] = [i, 0]
      else:
         table[j][-1] = i
      prefix += prefix[-1] + j,
      negative += negative[-1],
      if j < 0:
         negative[-1] += j

   ans = float('-inf')
   for i,j in table.values():
      if j != 0:
         sm1 = prefix[j+1] - prefix[i]
         sm2 = negative[j] - negative[i+1] if j > i+1 else 0
         ans = max(ans, sm1 - sm2)
   return ans

print(solve([3, 4, 5, 3, 4]))

อินพุต

[3, 4, 5, 3, 4]

ผลลัพธ์

16