โปรแกรมหาผลรวมถ่วงน้ำหนักสูงสุดของอาร์เรย์หมุนเวียนใน Python

มีอาร์เรย์ ต้องหาผลรวมถ่วงน้ำหนัก (weighted sum) สูงสุดเมื่อหมุนเวียนอาร์เรย์ น้ำหนักคือ S = Σ i * nums[i] (1-indexed)

ตัวอย่าง: L=[5,3,4] ผลลัพธ์ 26 (หมุนเป็น [3,4,5]: 1×3+2×4+3×5=26)

วิธีแก้ปัญหา (O(n) Formula)

1. sum_a = sum(nums)
2. cur = ans = Σ nums[i]*(i+1)
3. วน i=0..n-1: cur = cur - sum_a + nums[i]*n, ans = max(ans, cur)

เหตุผล: หมุนซ้าย 1 ตำแหน่ง ทุกค่าลดน้ำหนัก 1 (ลบ sum_a) ตัวแรกกลายเป็นตัวสุดท้ายน้ำหนัก n (บวก nums[i]*n)

ตัวอย่างโค้ด

def solve(nums):
    n = len(nums)
    sum_a = sum(nums)
    cur_val = ans = sum(nums[i] * (i+1) for i in range(n))
    for i in range(n):
        cur_val = cur_val - sum_a + nums[i] * n
        ans = max(ans, cur_val)
    return ans

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

อินพุต

[5,3,4]

เอาต์พุต

26