Solutions of Maximum subarray sum 3

Select solution language

noice Created at 0 likes

## Bài toán yêu cầu bạn tìm tổng lớn nhất từ ba dãy con khác rỗng không giao nhau. ## Một hướng giải là sử dụng [Thuật toán Kadane](https://vi.wikipedia.org/wiki/B%C3%A0i_to%C3%A1n_m%E1%BA%A3ng_con_l%E1%BB%9Bn_nh%E1%BA%A5t) để tìm tổng lớn nhất cho mỗi dãy con. Có thể giải như sau: - Hiểu thuật toán -- Khi bạn xét đến phần tử thứ $i$ trong mảng, thì một là bạn nối tiếp dãy con đang có và cộng giá trị đó vào tổng, hai là tạo dãy con mới từ phần tử đó. Từ đó, tổng $S$ lớn nhất của một dãy con có thể được tính bằng: \begin{equation} S = max(S + A[i], S). \end{equation} - Với thuật toán này, bạn sẽ xây dựng lần lượt để tìm tổng lớn nhất từ ba dãy con. Bạn sẽ xét đến dãy con thứ ba trước, vì nó sẽ phụ thuộc vào tổng lớn nhất tìm được từ hai dãy con trước đó, tương tự dãy con thứ hai sẽ phụ thuộc vào tổng của dãy con độc lập đầu tiên. ### Code tham khảo: ``` #include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int INF = 1e9 + 9; const int LIM = 1e5 + 5; int n, shelf[LIM]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; ++i) cin >> shelf[i]; int cur1 = 0, cur2 = 0, cur3 = 0; int best1 = -INF, best2 = -INF, best3 = -INF; for (int i = 1; i <= n; ++i) { cur3 = max(cur3 + shelf[i], best2 + shelf[i]); best3 = max(best3, cur3); cur2 = max(cur2 + shelf[i], best1 + shelf[i]); best2 = max(best2, cur2); cur1 = max(cur1 + shelf[i], shelf[i]); best1 = max(best1, cur1); } cout << best3; }