โปรแกรมหาค่า Power สูงสุดของลิสต์โดยย้ายสมาชิกใน Python

ได้รับลิสต์ nums จำนวนบวก N ตัว อนุญาตให้ ย้าย (ไม่ใช่ส왑) สมาชิกตัวใดตัวหนึ่งไปตำแหน่งอื่นได้ 1 ครั้ง (หรือไม่ย้ายก็ได้) หา Power สูงสุด ที่เป็นไปได้

Power = Σ (i+1) × nums[i] สำหรับ i = 0 ถึง N-1

ตัวอย่าง

Input: [6, 2, 3]

Output: 26

ย้าย 6 ไปท้าย → [2, 3, 6] → Power = 2×1 + 3×2 + 6×3 = 26

แนวทางแก้ปัญหา

ใช้ Prefix Sum คำนวณผลกระทบของการย้าย:

• base = power เดิม
• P[i] = prefix sum จนถึง i (P[0]=0, P[1]=nums[0], ...)
• ลองย้ายสมาชิก nums[i] ไปตำแหน่ง j:
  • Δ = P[i] - P[j] - (i - j) × nums[i]
  • คำตอบ = max(base + Δ) สำหรับทุกคู่ (i, j)

การใช้งาน (Python)

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
        n = len(A)
        for i, x in enumerate(A):
            for j in range(n + 1):
                ans = max(ans, base + P[i] - P[j] - (i - j) * x)
        return ans

# ทดสอบ
ob = Solution()
print(ob.solve([6, 2, 3]))  # Output: 26

ความซับซ้อน

• Time Complexity: O(N²)
• Space Complexity: O(N)

หมายเหตุ: สามารถปรับปรุงเป็น O(N log N) หรือ O(N) ได้ด้วย Convex Hull Trick หรือการสังเกตเพิ่มเติม