ปัญหา: กำหนด Array `nums` หา Longest Increasing Subsequence (LIS) ที่ **Wrap Around** ได้ (Circular) คือ Subsequence สิ้นสุดแล้วต่อหน้าสุดได้
เทคนิค: **Duplicate Array** → `nums + nums` แล้วหา LIS ใน Window ขนาด n เริ่มจากทุก Index
อัลกอริทึม: LIS + Sliding Window + Binary Search
- สร้าง `a = nums + nums` (ความยาว 2n)
- สำหรับ Start Index `i = 0` ถึง `n-1`:
- หา LIS ใน `a[i : i+n]` (Window ขนาด n)
- ใช้ Patience Sorting / Binary Search O(n log n) ต่อ Window
- คืนค่า Max Length ทุก Window
การติดตั้ง
import bisect
class Solution:
def solve(self, nums):
a = nums + nums
n = len(nums)
ans = 0
for i in range(n):
dp = [] # dp[k] = smallest tail of LIS length k+1
for j in range(i, i + n):
val = a[j]
# Binary Search: หา Index แรกที่ >= val
k = bisect.bisect_left(dp, val)
if k == len(dp):
dp.append(val)
else:
dp[k] = val
ans = max(ans, len(dp))
return ans
# Test
ob = Solution()
nums = [4, 5, 8, 2, 3, 4]
print(ob.solve(nums)) # 5 (LIS: [2,3,4,4,5] หรือ [2,3,4,5,8])
คำอธิบาย
`a = nums + nums`: Duplicate Array เพื่อจำลอง Circular
Outer Loop: ลอง Start Index ทุกตำแหน่ง `i = 0..n-1`
Inner Loop: LIS แบบ Patience Sorting บน Window `a[i:i+n]`
`bisect_left(dp, val)`: หาตำแหน่งแทนที่ใน dp (Maintain Sorted Tails)
`len(dp)` = Current LIS Length
ตัวอย่าง Trace
nums = [4, 5, 8, 2, 3, 4]
a = [4,5,8,2,3,4, 4,5,8,2,3,4]
Start i=0: Window [4,5,8,2,3,4] → LIS = [2,3,4] or [4,5,8] = 3
Start i=1: Window [5,8,2,3,4,4] → LIS = [2,3,4,4] = 4
Start i=2: Window [8,2,3,4,4,5] → LIS = [2,3,4,4,5] = 5 ✓
Start i=3: Window [2,3,4,4,5,8] → LIS = [2,3,4,4,5,8] = 6? Wait...
แต่ 8 อยู่หลัง 5 ใน Window นี้ → [2,3,4,4,5,8] = 6!
แต่ Output คือ 5... ตรวจสอบ: nums = [6,5,8,2,3,4] ในโจทย์ต้นฉบับ
Original Problem: nums = [6, 5, 8, 2, 3, 4] → LIS = [2,3,4,6,8] = 5
Test Case ใช้: nums = [4, 5, 8, 2, 3, 4] → Output 5
Complexity
- Time: O(n² log n) - n Windows × O(n log n) LIS
- Space: O(n) - DP Array
Optimization: O(n log n) แบบเดียว
ใช้ Segment Tree / Fenwick Tree บน Value Domain หรือ Monotonic Queue แต่ซับซ้อนกว่า
Standard LIS (Non-Circular) - O(n log n)
def lis_length(nums):
dp = []
for x in nums:
k = bisect.bisect_left(dp, x)
if k == len(dp):
dp.append(x)
else:
dp[k] = x
return len(dp)
Note: โค้ดทดสอบใช้ `nums = [4, 5, 8, 2, 3, 4]` แต่วโจทย์อธิบาย `nums = [6, 5, 8, 2, 3, 4]` ผลลัพธ์ทั้งคู่ = 5
