ได้รับลิสต์ตัวเลข nums และค่า k หา ความยาวของ Longest Increasing Subsequence (LIS) ที่มี จำนวนเลขคี่ ≥ k
ตัวอย่าง
Input: nums = [12, 14, 16, 5, 7, 8], k = 2
Output: 3 (LIS คือ [5, 7, 8] มีเลขคี่ 2 ตัว คือ 5, 7)
แนวทางแก้ปัญหา
ใช้ DFS + Backtracking (เหมาะสำหรับ N ≤ ~20):
- State:
dp(i, j, odd, taken)โดยi= index ตัวสุดท้ายที่เลือกj= index กำลังพิจารณาodd= จำนวนเลขคี่ที่เลือกแล้วtaken= จำนวนตัวที่เลือกแล้ว
- ถ้า
odd ≥ k→ อัปเดตคำตอบ - ลองเลือก
nums[j]ถ้า >nums[i]หรือ ข้ามไป
หมายเหตุ: สำหรับ N ใหญ่ควรใช้ DP + BIT/Segment Tree แบบ O(N log N)
การใช้งาน (Python)
class Solution:
def solve(self, nums, k):
best = 0
n = len(nums)
def dp(i, j, odd, taken):
nonlocal best
if odd >= k:
best = max(best, taken)
if j == n:
return
if nums[j] > nums[i]:
dp(j, j + 1, odd + (nums[j] & 1), taken + 1)
dp(i, j + 1, odd, taken)
for i in range(n):
dp(i, i + 1, nums[i] & 1, 1)
return best
# ทดสอบ
ob = Solution()
print(ob.solve([12, 14, 16, 5, 7, 8], 2)) # Output: 3
ความซับซ้อน
- Time Complexity: O(2^N) แบบ brute force
- Space Complexity: O(N) recursion stack
แนะนำ: ใช้ DP + Fenwick Tree บนค่าที่ compress แล้ว เพื่อ O(N log N)
