ได้รับลิสต์จำนวนไม่ติดลบ และ k หา ผลรวม subsequence สูงสุดที่หาร k ลงตัว
ตัวอย่าง
Input: nums = [4, 6, 8, 2], k = 2
Output: 20 (sum ทั้งหมด = 20 หาร 2 ลงตัว)
แนวทางแก้ปัญหา
ข้อสังเกต: ถ้า sum ทั้งหมดหาร k ลงตัว → คำตอบคือ sum ทั้งหมด มิฉะนั้น ต้องลบ subsequence ที่มีผลรวม ≡ remainder (mod k) และมีค่าน้อยที่สุด
แต่โค้ดต้นฉบับใช้ brute force ทุก subset (itertools.combinations) → ใช้ได้เฉพาะ N ≤ ~20
การใช้งาน (Python - รุ่นต้นฉบับ Brute Force)
from itertools import chain, combinations
class Solution:
def solve(self, nums, k):
total = sum(nums)
rem = total % k
if rem == 0:
return total
nums.sort()
# ลองทุก subset หา sum ที่ ≡ rem (mod k) และน้อยที่สุด
for r in range(1, len(nums) + 1):
for combo in combinations(nums, r):
s = sum(combo)
if s % k == rem:
return total - s
return 0
วิธีที่ดีกว่า: DP O(N×K)
class Solution:
def solve(self, nums, k):
# dp[r] = max sum ที่ได้ remainder r
dp = [-float('inf')] * k
dp[0] = 0
for x in nums:
new_dp = dp[:]
for r in range(k):
if dp[r] != -float('inf'):
nr = (r + x) % k
new_dp[nr] = max(new_dp[nr], dp[r] + x)
dp = new_dp
return dp[0]
ความซับซ้อน
- Brute Force: O(2^N) - ใช้ได้เฉพาะ N เล็ก
- DP: O(N × K) - ใช้ได้กับ N, K ใหญ่
