a605. 交錯和 - 高中生程式解題系統

內容

給定一個整數數列

a = a_{1}, a_{2}, \dots, a_{n}

。對於每個下標數列

i = i_{1}, i_{2}, \dots, i_{m}

，其中

m \neq 0

且

1 \leq i_{1} < i_{2} < \dots < i_{m} \leq n

，我們定義交錯和

σ (i; a)

為

a_{i_{1}} - a_{i_{2}} + a_{i_{3}} - a_{i_{4}} + \dots + (- 1)^{m - 1} a_{i_{m}}

。

已知對於所有

1

到

m - 1

之間的整數

j

，均有

i_{j + 1} - i_{j} \leq δ

，請求出

σ (i; a)

的最大值。

輸入說明

$n$ $δ$

$a_{1}$ $a_{2}$ $\dots$ $a_{n}$

$1 \leq n \leq 10^{6}$ 。
$1 \leq δ \leq n$ 。
對於所有的 $k \in {1, 2, \dots, n}$ ，均有 $- 2^{31} \leq a_{k} \leq 2^{31} - 1$ 。
輸入的數皆為整數。

輸出說明

S

$S$ 為一整數，代表在滿足 $i_{j + 1} - i_{j} \leq δ$ 的限制下， $σ (i; a)$ 的最大值。

範例輸入 #1

5 1
1 4 3 2 5

範例輸出 #1

範例輸入 #2

5 2
1 4 3 2 5

範例輸出 #2

範例輸入 #3

10 4
-10 -9 -8 -7 -6 -5 -4 -3 -2 -1

範例輸出 #3

-1

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (20%): 0.2s , <1K
不公開測資點#1 (20%): 0.2s , <1M
不公開測資點#2 (20%): 0.2s , <1M
不公開測資點#3 (20%): 0.2s , <10M
不公開測資點#4 (20%): 0.2s , <10M

提示：

標籤:

出處:

原創問題，如有雷同，純屬巧合 [管理者： xavier13540 (柊四千) ]

編號	身分	題目	主題	人氣	發表日期
40024	xavier13540 (柊四千)	a605	作者提供的解法	171	2024-04-22 15:05