MaximumNonAdj - Tổng không liên tục lớn nhất

(codelearn.io Advanced Algorithms - Dynamic Programming, problem 6)
Updated $\LaTeX$, 2022

Đề bài

Cho một mảng gồm các số nguyên. Hãy tìm tổng lớn nhất của tất cả các chuỗi con mà không có 2 phần tử nào đứng cạnh nhau trong chuỗi con đó.

Input: mảng số nguyên $arr$, $0 \leq |arr| \leq 10^6$.
Output: số nguyên là tổng lớn nhất thỏa yêu cầu đề bài.

Ví dụ

Input: $arr = [1, 4, 1]$
Output: $4$

Giải thích: Các chuỗi con mà không có $2$ phần tử nào đứng cạnh nhau là $\{1\}, \{4\}, \{1\}, \{1, 1\}$, trong đó chuỗi con có tổng lớn nhất là $\{4\}$.

Solution

Quy hoạch động

Ta chèn một số $0$ vào trước mảng cần xét. Theo ví dụ, mảng sau khi chèn số $0$ sẽ trở thành $arr = [0, 1, 4, 1]$. Gọi $F_i$ là tổng lớn nhất của chuỗi con có phần tử cuối ở vị trí $i$.

• $F_0 := 0$ do vị trí $0$ vừa chèn vào không tồn tại trong mảng ban đầu;
• $F_1$ là tổng lớn nhất của chuỗi con có phần tử cuối tại vị trí $1$. Tại vị trí $1$ chỉ có $1$ phần tử, nên nghiễm nhiên $F_1 := arr_1$. Tuy nhiên, ta phải xét $2$ trường hợp:
• $arr_1 \geq 0$. Khi đó nếu gán $F_1 := arr_1$ thì $F_1$ là một số dương, vẫn có thể là tổng lớn nhất của cả dãy số.
• $arr_1 < 0$. Khi đó $F_1 = arr_1$ thì $F_1$ là một số âm. Tại đây có thể gây bug, nếu $F_1$ cộng vào một số dương ở phía sau sẽ cho kết quả sai. Do đó nếu $arr_1$ âm thì ta lấy $F_1 := 0$, nếu có một số dương ở phía sau cộng vào sẽ không cho kết quả sai.

Công thức truy hồi:

$\left\{\begin{aligned}F_0 &:= 0 \\ F_1 &:= \max(arr_1, 0) \\ F_i &:= \max(arr_i + F_{i - 2}, F_{i - 1})\ (i \geq 2)\end{aligned}\right.$

Kết quả sẽ là $\max(F)$.

Note: bài này yếu không có trường hợp tất cả số trong dãy cho trước là số âm. Với trường hợp này, kết quả sẽ là $\max(arr)$.

Code C++:

Code Python: