โปรแกรมเพื่อค้นหาพลังสุดท้ายของรายการใน Python

สมมติว่าเรามีรายการและกำลังของรายการถูกกำหนดโดยผลรวมของ (ดัชนี + 1) * value_at_index ของดัชนีทั้งหมด อีกทางหนึ่ง เราสามารถแสดงได้ดังนี้ −

$$\displaystyle\sum\limits_{i=0}^{n-1} (i+1)\times list[i]$$

ตอนนี้ เรามีรายการจำนวนที่มีจำนวนเต็มบวก N เราสามารถเลือกค่าเอกพจน์ในรายการ และย้าย (ไม่สลับ) ไปยังตำแหน่งใดๆ ก็ได้ สามารถเลื่อนไปที่จุดเริ่มต้นของรายการหรือสิ้นสุดได้ เรายังสามารถเลือกไม่ย้ายตำแหน่งได้เลย เราต้องหากำลังสุดท้ายที่เป็นไปได้สูงสุดของรายการ ผลลัพธ์จะต้องถูกดัดแปลงโดย 10^9 + 7

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

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

• ป :=[0]

• ฐาน :=0

• สำหรับแต่ละ i, x ในดัชนี i และรายการ x ใน A, 1, ทำ

  • แทรก P[-1] + x ที่ส่วนท้ายของ P

  • ฐาน :=ฐาน + i * x

• กำหนดฟังก์ชัน eval_at() นี่จะใช้เวลา j, x

  • กลับ -j * x + P[j]

• กำหนดฟังก์ชัน intersection() นี่จะใช้เวลา j1, j2

  • ผลตอบแทน(P[j2] - P[j1]) /(j2 - j1)

• ตัวถัง :=[-1]

• ดัชนี :=[0]

• สำหรับ j ในช่วง 1 ถึงขนาด P ให้ทำ

  • ขณะที่ตัวเรือและทางแยก(indexes[-1], j) <=hull[-1], ทำ

    • ลบองค์ประกอบสุดท้ายออกจากตัวถัง

    • ลบองค์ประกอบสุดท้ายออกจากดัชนี

  • แทรกจุดตัด(ดัชนี[-1], j) ที่ส่วนท้ายของตัวถัง

  • แทรก j ที่ส่วนท้ายของดัชนี

• ตอบ :=ฐาน

• สำหรับแต่ละ i, x ในดัชนี i และรายการ x ใน A, ทำ

  • j :=ส่วนที่สามารถแทรก x ลงในตัวถังได้ โดยคงลำดับการจัดเรียง

  • j :=สูงสุด j - 1, 0

  • ans :=สูงสุดของ ans, ฐาน + eval_at(i, x) - eval_at(indexes[j], x)

• ส่งคืน mod (10^9 + 7)

ตัวอย่าง

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

import bisect
class Solution:
   def solve(self, A):
      P = [0]
      base = 0
      for i, x in enumerate(A, 1):
         P.append(P[-1] + x)
         base += i * x
      def eval_at(j, x):
         return -j * x + P[j]
      def intersection(j1, j2):
         return (P[j2] - P[j1]) / (j2 - j1)
      hull = [-1]
      indexes = [0]
      for j in range(1, len(P)):
         while hull and intersection(indexes[-1], j) <= hull[-1]:
            hull.pop()
            indexes.pop()
         hull.append(intersection(indexes[-1], j))
         indexes.append(j)
      ans = base
      for i, x in enumerate(A):
         j = bisect.bisect(hull, x)
         j = max(j - 1, 0)
         ans = max(ans, base + eval_at(i, x) - eval_at(indexes[j], x))
      return ans % (10 ** 9 + 7)

ob = Solution()
print (ob.solve([4, 2, 1]))

อินพุต

[4, 2, 1]

ผลลัพธ์

16