โปรแกรมรับค่าพลังสูงสุดของรายการโดยจัดเรียงองค์ประกอบใหม่ใน Python

สมมติว่าเรามีรายการจำนวน N จำนวนบวก ตอนนี้ เราสามารถเลือกค่าใดค่าหนึ่งจากรายการ และย้าย (ไม่สลับ) ไปยังตำแหน่งใดก็ได้ เราไม่สามารถขยับตำแหน่งใดๆ ได้เลย ดังนั้นเราต้องค้นหาว่าอำนาจสุดท้ายที่เป็นไปได้สูงสุดของรายการคืออะไร? ดังที่เราทราบกำลังของรายการคือผลรวมของ (index + 1) * value_at_index ของดัชนีทั้งหมด i.

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

ดังนั้น หากอินพุตเป็น nums =[6, 2, 3] เอาต์พุตจะเป็น 26 เนื่องจากเราสามารถย้าย 6 ไปยังจุดสิ้นสุดเพื่อรับรายการ [2, 3, 6] ดังนั้นกำลังจึงเป็น:(2 * 1) + (3 * 2) + (6 * 3) =26.

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

• P :=รายการที่มีค่า 0

• ฐาน :=0

• สำหรับแต่ละดัชนี i และค่า x ของ A ทำ

  • แทรกองค์ประกอบสุดท้ายของ P + x ที่ส่วนท้ายของ P

  • ฐาน :=ฐาน + (i+1) * x

• ตอบ :=ฐาน

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

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

    • ans :=สูงสุดของ ans และ (ฐาน + P[i] - P[j] -(i - j) * x)

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

ตัวอย่าง

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

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
      ans = base
      for i, x in enumerate(A):
         for j in range(len(A) + 1):
            ans = max(ans, base + P[i] - P[j] - (i - j) * x)
      return ans
ob = Solution()
nums = [6, 2, 3]
print(ob.solve(nums))

อินพุต

[6, 2, 3]

ผลลัพธ์

26