題目：
給定一個長度為 N 的整數序列：A1, A2, · · · , AN。現在你有一次機會，將其中連續的 K 個數修改成任意一個相同值。請你計算如何修改可以使修改后的數列的最長不下降子序列最長，請輸出這個最長的長度。?
最長不下降子序列是指序列中的一個子序列，子序列中的每個數不小于在它之前的數。?
輸入格式
輸入第一行包含兩個整數 N 和 K。
第二行包含 N 個整數 A1, A2, · · · , AN。?
輸出格式
輸出一行包含一個整數表示答案。
（1）代碼：
?
##########################輸入部分
n, k = map(int, input().split())
arr = [int(i) for i in input().split()]
?
l = n
notk_max = 0
zd = [0 for i in range(l)]
?
######################################代碼部分
?
def bs(t,a,mid):
? ? if t:
? ? ? ? return mid <= a
? ? else:
? ? ? ? return mid >= a
?
?
def erf(t,dp,a):#找到新元素在單調棧中的位置,t為False是自左往右第一個小于a，t為True是自左往右第一個大于a
? ? if not dp:
? ? ? ? return -1
? ? l,r=0,len(dp)-1
? ? while l<r:
? ? ? ? mid=(l+r)//2
? ? ? ? if bs(t,a,dp[mid]):#縮頭
? ? ? ? ? ? l=mid+1
? ? ? ? else:
? ? ? ? ? ? r=mid
? ? return -1 if bs(t,a,dp[l]) else l
?
def zhao2(): ?# 得出以我結尾的的最長子序列
? ? global zd, notk_max, arr, k, l
? ? dp = []
? ? for i in range(l - k):
? ? ? ? wz = erf(True, dp, arr[i])
? ? ? ? if wz < 0:
? ? ? ? ? ? dp.append(arr[i])
? ? ? ? ? ? zd[i] += len(dp)
? ? ? ? else:
? ? ? ? ? ? dp[wz] = arr[i]
? ? ? ? ? ? zd[i] += (wz + 1)
? ? ? ? if zd[i] > notk_max:
? ? ? ? ? ? notk_max = zd[i]
?
?
def zhao1(): ?# 得出以我開頭的最長子序列 (不包括自己)，以及k在最左側的not_kmax
? ? global zd, notk_max, arr, k, l
? ? dp = []
? ? for i in range(l - 1, k, -1):
? ? ? ? wz = erf(False, dp, arr[i])
? ? ? ? if wz < 0:
? ? ? ? ? ? dp.append(arr[i])
? ? ? ? else:
? ? ? ? ? ? dp[wz] = arr[i]
? ? ? ? #######以下為zd賦值
? ? ? ? wz = erf(False, dp, arr[i - k - 1])
? ? ? ? if wz < 0:
? ? ? ? ? ? zd[i - k - 1] = len(dp)
? ? ? ? else:
? ? ? ? ? ? zd[i - k - 1] = wz
? ? ########以下得出k覆蓋最左 最長不下降子序列長度
? ? notk_max = len(dp)
? ? wz = erf(False, dp, arr[k])
? ? if wz < 0:
? ? ? ? notk_max += 1
?
?
##############################################輸出部分
zhao1()
zhao2()
print(notk_max + k)
（1）解析：
1.在代碼中的前兩個函數為輔助判斷二次搜查
def bs(t,a,mid):
? ? if t:
? ? ? ? return mid <= a
? ? else:
? ? ? ? return mid >= a
?
?
def erf(t,dp,a):#找到新元素在單調棧中的位置,t為False是自左往右第一個小于a，t為True是自左往右第一個大于a
? ? if not dp:
? ? ? ? return -1
? ? l,r=0,len(dp)-1
? ? while l<r:
? ? ? ? mid=(l+r)//2
? ? ? ? if bs(t,a,dp[mid]):#縮頭
? ? ? ? ? ? l=mid+1
? ? ? ? else:
? ? ? ? ? ? r=mid
? ? return -1 if bs(t,a,dp[l]) else l
首先我們用t = True，來表示找到在dp這個列表中，比a大的數，首先用二分搜查，來確定比a大的屬的序列在哪里，用輔助函數bs來判斷，當t為True時，dp[mid]比a小，說明此時mid不是我們要找的序列，將l更新，直到找到我們需要的序列，最后返回l
接下來對主題函數的思想進行分析，首先將k想象為一個可以覆蓋元素的滑動窗口，自左往右滑動，k每滑動一次我們就從沒有被k覆蓋的元素中找最長不下降子序列。而k自左往右滑動完，出現過的最長的最長不下降子序列的長度＋k就是我們要的答案
案例 ：1，4，2，8，5 ? 。k=2 ? ? max=0
（1）k覆蓋1，4。從剩余的2，8，5找得最長不下降子序列，2，8。或2，5。max=2
（2）k覆蓋4，2。從剩余的1，8，5找得最長不下降子序列 1，8。1，5。max不變
（3）k覆蓋2，8。從剩余的1，4，5找得最長不下降子序列1，4，5。max=3
（4）k覆蓋8，5。.........max不變
最終max+k就是我們要的答案
2.zhao2的作用是將前（n-k）個數的最佳排序調整到notk——max，并解釋一下global用法，用 global 之后的變量將不只局限函數，而是放大于整體程序，在函數中變量的變值可以在函數以外的程序中使用
def zhao2(): ?# 得出以我結尾的的最長子序列
? ? global zd, notk_max, arr, k, l
? ? dp = []
? ? for i in range(l - k):（此時l為n）
? ? ? ? wz = erf(True, dp, arr[i])
? ? ? ? if wz < 0:
? ? ? ? ? ? dp.append(arr[i])
? ? ? ? ? ? zd[i] += len(dp)
? ? ? ? else:
? ? ? ? ? ? dp[wz] = arr[i]
? ? ? ? ? ? zd[i] += (wz + 1)
? ? ? ? if zd[i] > notk_max:
? ? ? ? ? ? notk_max = zd[i]
| 關鍵操作 | 作用 |
|---|---|
erf(True, dp, arr[i]) | 找到?arr[i]?在?dp?中的插入位置（第一個?>arr[i]?的數）。 |
dp.append(arr[i]) | 擴展 LNDS 長度（當前數字比所有?dp?值大）。 |
dp[wz] = arr[i] | 替換?dp?中的值，保持最小末尾（優化后續可能性）。 |
zd[i]?賦值 | 記錄以?arr[i]?結尾的 LNDS 長度。 |
第1步：處理?arr[0] = 3
- ?查找插入位置：
erf(True, [], 3)?→ 空棧直接返回?-1。
- ?更新?
dp?和?zd：wz = -1?→ 執行?dp.append(3)?→?dp = [3]。zd[0] = len(dp) = 1（以?3?結尾的 LNDS 長度為 1）。
- ?更新全局最大值：
notk_max = max(0, 1) = 1。
| i | arr[i] | dp 變化 | zd | notk_max |
|---|---|---|---|---|
| 0 | 3 | [3] | [1,0,0,0,0] | 1 |
?第2步：處理?arr[1] = 1
- ?查找插入位置：
erf(True, [3], 1)?→ 找第一個?>1?的數（3?在索引?0）。- 返回?
0。
- ?更新?
dp?和?zd：wz = 0?→ 替換?dp[0] = 1?→?dp = [1]。zd[1] = wz + 1 = 1（以?1?結尾的 LNDS 長度為 1）。
- ?全局最大值：
notk_max?保持?1（未更新）。
| i | arr[i] | dp 變化 | zd | notk_max |
|---|---|---|---|---|
| 1 | 1 | [1] | [1,1,0,0,0] | 1 |
?第3步：處理?arr[2] = 4
- ?查找插入位置：
erf(True, [1], 4)?→ 找第一個?>4?的數（無，返回?-1）。
- ?更新?
dp?和?zd：wz = -1?→?dp.append(4)?→?dp = [1, 4]。zd[2] = len(dp) = 2（以?4?結尾的 LNDS 為?[1, 4]）。
- ?全局最大值：
notk_max = max(1, 2) = 2。
| i | arr[i] | dp 變化 | zd | notk_max |
|---|---|---|---|---|
| 2 | 4 | [1, 4] | [1,1,2,0,0] | 2 |
?第4步：處理?arr[3] = 2
- ?查找插入位置：
erf(True, [1, 4], 2)?→ 找第一個?>2?的數（4?在索引?1）。- 返回?
1。
- ?更新?
dp?和?zd：wz = 1?→ 替換?dp[1] = 2?→?dp = [1, 2]。zd[3] = wz + 1 = 2（以?2?結尾的 LNDS 為?[1, 2]）。
- ?全局最大值：
notk_max?保持?2。
| i | arr[i] | dp 變化 | zd | notk_max |
|---|---|---|---|---|
| 3 | 2 | [1, 2] | [1,1,2,2,0] | 2 |
?3. 最終結果
zd = [1, 1, 2, 2, 0]：zd[0]=1：子序列?[3]zd[1]=1：子序列?[1]zd[2]=2：子序列?[1, 4]zd[3]=2：子序列?[1, 2]
notk_max = 2（前?n-k=4?個元素的最長 LNDS 長度）。
3.接下來為后（n-k）個元素的最佳排序，首先對
從右向左掃描，計算以每個位置開頭的 LNDS 長度
?
| 變量 | 作用 |
|---|---|
dp | 動態維護的單調棧（反向遞減），存儲 ?不同長度反向 LNDS 的最大起始值 |
zd[i] | 記錄以?arr[i]?開頭的 LNDS 長度（用于后續拼接） |
notk_max | 全局最大值，記錄反向掃描后的最長 LNDS 長度（用于處理?k?在最左側的情況） |
def zhao1(): ?# 得出以我開頭的最長子序列 (不包括自己)，以及k在最左側的not_kmax
? ? global zd, notk_max, arr, k, l
? ? dp = []
? ? for i in range(l - 1, k, -1):
? ? ? ? wz = erf(False, dp, arr[i])
? ? ? ? if wz < 0:
? ? ? ? ? ? dp.append(arr[i])
? ? ? ? else:
? ? ? ? ? ? dp[wz] = arr[i]
? ? ? ? #######以下為zd賦值
? ? ? ? wz = erf(False, dp, arr[i - k - 1])
? ? ? ? if wz < 0:
? ? ? ? ? ? zd[i - k - 1] = len(dp)
? ? ? ? else:
? ? ? ? ? ? zd[i - k - 1] = wz
? ? ########以下得出k覆蓋最左 最長不下降子序列長度
? ? notk_max = len(dp)
? ? wz = erf(False, dp, arr[k])
? ? if wz < 0:
? ? ? ? notk_max += 1
在wz = erf(False, dp, arr[i - k - 1])以上的代碼用于更新dp之后的代碼適用于將前（n-k）個數與后（n-k）連接起來
i - k - 1?的物理意義
- ?**
i**：當前反向遍歷的位置（從?n-1?到?k+1）。 - ?**
k**：允許修改的連續元素個數。 - ?**
i - k - 1：
?表示前?n - k?個元素中，與當前反向位置?i?對應的“連接點”?**。
這個位置是 ?前?n - k?個元素的尾部，用于檢查是否能與后?n - k?個元素的頭部拼接。
??為什么需要?i - k - 1？
- ?動態拼接的核心：
修改?k?個元素后，前?n - k?和后?n - k?部分的子序列需要通過某個值連接。
i - k - 1?標記了前?n - k?部分的最后一個元素，用于判斷是否能與后?n - k?部分的第一個元素形成不下降序列。
?具體例子說明
輸入：arr = [3, 1, 4, 2, 8]，n=5，k=1（修改 1 個元素）。
- ?前?
n - k = 4?個元素：[3, 1, 4, 2]（不修改部分）。 - ?反向遍歷范圍：
i = 4, 3, 2（對應?arr[4]=8,?arr[3]=2,?arr[2]=4）。
?步驟解析：?
-
?**
i = 4（arr[4] = 8）?**：i - k - 1 = 2（即?arr[2] = 4）。- ?作用：檢查?
4（前部分的最后一個值）是否能與?8（后部分的第一個值）拼接。- 若?
4 <= 8，則可以連接，此時?zd[2]?記錄反向 LNDS 長度。 - 本例中?
4 <= 8，zd[2]?被更新為反向長度?1（[8]）。
- 若?
-
?**
i = 3（arr[3] = 2）?**：i - k - 1 = 1（即?arr[1] = 1）。- ?作用：檢查?
1?是否能與?2?拼接。1 <= 2，可以連接，zd[1]?更新為反向長度?2（[2, 8]）。
-
?**
i = 2（arr[2] = 4）?**：i - k - 1 = 0（即?arr[0] = 3）。- ?作用：檢查?
3?是否能與?4?拼接。3 <= 4，可以連接，zd[0]?更新為反向長度?2（[4, 8]）。
?關鍵作用總結
| 場景 | i - k - 1?的作用 |
|---|---|
| ?反向遍歷時 | 定位前?n - k?個元素的尾部（arr[i - k - 1]），判斷是否能與后?n - k?的頭部連接。 |
?更新?zd | 記錄前?n - k?個元素中每個位置能向后延伸的 LNDS 長度，用于后續全局拼接。 |
?修改?k?的靈活性 | 通過?zd?和?notk_max?的配合，動態計算修改?k?個元素后的最優解。 |
??為什么這樣設計？
- ?高效性：避免顯式枚舉所有可能的修改方案，通過反向掃描直接計算可能的最優連接點。
- ?正確性：確保前?
n - k?和后?n - k?部分的子序列能通過某個值（可能是修改后的?k?個元素）無縫拼接。
??最終結果的意義
- ?**
zd?數組**：zd[i]?表示以?arr[i]?開頭或結尾的 LNDS 長度。- 例如?
zd = [2, 2, 1, 2, 0]?表示：- 從?
3?開頭的 LNDS 長度為 2（[3, 4]）。 - 從?
1?開頭的 LNDS 長度為 2（[1, 2]）。
- 從?
- ?**
notk_max + k**：
結合正向和反向結果，允許修改?k?個元素時的最長 LNDS（如?[1, 4, 8]?長度為 3）。
?總結
i - k - 1?是算法中 ?連接前后子序列的橋梁，通過反向掃描動態更新?zd?數組，確保能高效計算出修改?k?個元素后的最優解。其核心思想是：
?“前?n - k?的末尾必須 ≤ 后?n - k?的開頭”?，而?i - k - 1?正是找到這個關鍵連接點的索引。
4.接下來解釋如何取得最大的值
首先我們已經取得了前（n-k）個數和后（n-k）個數的最佳排序，用notk_max代替兩個值相加，再用其加上k即可
notk_max = len(dp)
? ? wz = erf(False, dp, arr[k])
? ? if wz < 0:
? ? ? ? notk_max += 1
數字示例
?輸入：
arr = [3, 1, 4, 2, 8]，n=5，k=1（修改 1 個元素）。- ?前?
n-k=4?個元素：[3, 1, 4, 2]。 - ?后?
n-k=4?個元素：[1, 4, 2, 8]（反向掃描從?i=4?到?i=1）。
?步驟解析：
?**(1)?zhao2()?正向掃描后：?**
zd = [1, 1, 2, 2, 0]（前?n-k?部分的 LNDS 長度）：zd[0]=1：[3]zd[1]=1：[1]zd[2]=2：[1,4]zd[3]=2：[1,2]
?**(2)?zhao1()?反向掃描時：?**
- ?初始化：
dp = []（反向單調棧），notk_max = 0。 - ?處理?
i=4（arr[4]=8）?：dp = [8]（反向 LNDS 長度?len(dp)=1）。i-k-1=2（arr[2]=4）：- 檢查?
4 <= 8（可以拼接）。 notk_max = max(0, zd[2] + len(dp)) = max(0, 2+1) = 3。
- 檢查?
- ?處理?
i=3（arr[3]=2）?：dp = [8, 2]（反向 LNDS 長度?len(dp)=2）。i-k-1=1（arr[1]=1）：- 檢查?
1 <= 2（可以拼接）。 notk_max = max(3, zd[1] + len(dp)) = max(3, 1+2) = 3（未更新）。
- 檢查?
- ?處理?
i=2（arr[2]=4）?：dp = [8, 4]（替換?2?為?4，保持遞減）。i-k-1=0（arr[0]=3）：- 檢查?
3 <= 4（可以拼接）。 notk_max = max(3, zd[0] + len(dp)) = max(3, 1+2) = 3（未更新）。
- 檢查?
- ?最終?
notk_max = 3：- 對應子序列?
[1,4,8]（前?[1]?+ 后?[4,8]，修改?arr[0]=1）。
- 對應子序列?
?**(3) 輸出?notk_max + k = 3 + 1 = 4**：
- 實際最長 LNDS 為?
[1,1,4,8]（修改?arr[0]=1，長度 4）。
?關鍵點總結
| 操作 | 數學意義 | 示例中的作用 |
|---|---|---|
zd[i]（正向） | 前?n-k?部分以?arr[i]?結尾的 LNDS 長度。 | zd[2]=2?表示?[1,4]。 |
len(dp)（反向） | 后?n-k?部分以?arr[i]?開頭的 LNDS 長度。 | dp=[8,4]?表示?[4,8]。 |
notk_max?更新 | 取?zd[i-k-1] + len(dp)?的最大值，確保前后部分能拼接。 | max(3, 2+1)=3（[1,4,8]）。 |
+ k | 修改的?k?個元素作為橋梁，連接前后子序列。 | 長度?3 + 1 = 4（[1,1,4,8]）。 |
?為什么這樣能覆蓋所有情況？
- ?不修改?
k?的情況：
notk_max?已經記錄了前/后部分的最長拼接（如?[1,4,8]?長度 3）。 - ?修改?
k?的情況：
通過?+ k?直接擴展長度（如修改?arr[0]=1，得到?[1,1,4,8]?長度 4）。 - ?數學保證：
最長 LNDS 必然由以下兩種之一構成：- 不修改?
k?時的?notk_max。 - 修改?
k?時的?notk_max + k（因為修改的?k?個元素可以完美連接前后部分）。
- 不修改?
