โปรแกรมหาค่า Maximum ของ Valid Array ใน Python

ปัญหา

อาร์เรย์ nums แต่ละค่า = "Power" Array "Valid" ถ้า: ความยาว > 2 และค่าแรก = ค่าสุดท้าย ลบ Element บางส่วนเพื่อให้ Valid หา Maximum Sum ของ Valid Array

ตัวอย่าง

nums = [3, 4, 5, 3, 4] → Output: 16

ลบ 3 ตัวแรก → [4, 5, 3, 4] Valid (4=4, len=4) Sum = 16

อัลกอริทึม (Prefix Sum + First/Last Occurrence)

1. บันทึก First และ Last Occurrence ของแต่ละค่า
2. Prefix Sum สำหรับ Sum Range Query
3. Prefix Sum ของค่าลบ (Negative Prefix) เพื่อลบค่าลบระหว่าง First-Last
4. สำหรับแต่ละค่าที่มี First ≠ Last: Sum = Prefix[Last+1] - Prefix[First] - Negative_Between
5. หา Max

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

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.append(prefix[-1] + j)
        negative.append(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]))  # 16

ความซับซ้อน

• Time: O(n)
• Space: O(n)