Cho mảng nums n số nguyên (mỗi giá trị là 'power'). Mảng 'hợp lệ' (valid) nếu độ dài > 2 và phần tử đầu = phần tử cuối. Có thể xóa phần tử để tạo mảng hợp lệ. Tìm tổng power lớn nhất của mảng hợp lệ.
Ví dụ: nums = [3,4,5,3,4] → output = 16 (xóa 3 đầu → [4,5,3,4], sum=16).
Giải thuật (Prefix sum + First/Last occurrence)
- Lưu first và last occurrence của mỗi giá trị.
- Prefix sum của mảng gốc.
- Prefix sum của các giá trị âm (negative prefix).
- Với mỗi giá trị xuất hiện ≥ 2 lần: tổng đoạn [first, last] = prefix[last+1]-prefix[first]. Trừ đi tổng giá trị âm trong (first, last) để loại bỏ phần tử âm có thể bỏ qua.
- Lấy max.
Code Python
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
Đầu vào / Đầu ra
Input: [3, 4, 5, 3, 4]
Output: 16