## 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;
}
# Lời giải:
Có lẽ các bạn đã xem qua lời giải bằng thuật toán Kadane.
Vậy nên mình sẽ nói về một hướng giải khác bằng Quy hoạch động
Tóm tắt: đề bài yêu cầu tìm ra giá trị lớn nhất của tổng 3 đoạn con liên tiếp khác rỗng
- Gọi f[i][j][1] là giá trị lớn nhất có được nếu chọn phần tử thứ i và đoạn con liên tiếp đang chọn là j
ngược lại với f[i][j][0] tức ta không chọn phần tử thứ i
- Công thức truy hồi:
- f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1])
- f[i][j][1] = max(f[i-1][j-1][0], f[i-1][j][1]) + a[i];
- với i từ 1 -> n và j từ 0 -> 3
- Để dễ hiểu thì f[i][j][1] sẽ có 2 trường hợp như sau: Một là tiếp tục chọn từ đoạn con
liên tiếp đang tính, hai là bắt đầu một đoạn con liên tiếp mới
- Đáp án sẽ là max(f[n][j][0], f[n][j][1]) với j từ 0 -> 3 nếu trong mảng có ít nhất 3 phần tử không âm
vì đề bài yêu cầu là 3 đoạn con khác rỗng nên nếu có ít hơn 3 phần tử không âm trong mảng thì đáp án là tổng của 3 phần tử lớn nhất
- Độ phức tạp: O(n)
- Độ phức tạp của bộ nhớ: O(n)
- Lưu ý: có thể tối ưu độ phức tạp của bộ nhớ bằng cách sử dụng 2 mảng tính lại lẫn nhau,
giúp giảm xuống còn O(1) và với cách làm trên có thể giải quyết bài toán tổng quát
tìm ra giá trị lớn nhất của tổng k đoạn con liên tiếp khác rỗng hay thay đổi một chút
cũng có thể giải quyết bài toán tương tự (https://marisaoj.com/problem/147)
# Code tham khảo:
```
#include<bits/stdc++.h>
#define ll long long
#define nl '\n'
#define f0(i,a,b) for (int i = a, _b = b; i < _b; i++)
#define f1(i,a,b) for (int i = a, _b = b; i <= _b; i++)
#define rf(i,a,b) for (int i = a, _b = b; i >=_b; i--)
#define fi first
#define se second
using namespace std;
const int Maxn = 1e5+5;
const int Mod = 1e9+7;
const long long inf = 1e18+7;
int n;
int a[Maxn];
ll f[Maxn][10][5];
int b[Maxn];
int cnt = 0;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
f1(i,1,n) cin >> a[i], b[i] = a[i];
ll ans = 0;
f1(i,1,n)
{
f1(k,0,3)
{
f[i][k][0] = max(f[i-1][k][1], f[i-1][k][0]);
if (k > 0)
{
f[i][k][1] = max(f[i-1][k-1][0], f[i-1][k][1]) + a[i];
}
}
}
f1(i,0,3) f1(j,0,1) ans = max(ans, f[n][i][j]);
int cnt = 0;
f1(i,1,n) if (a[i] >= 0) cnt++;
if (cnt >= 3) cout << ans;
else
{
sort(b+1, b+n+1, greater<int>());
ll ma = 0;
f1(i,1,3) ma += b[i];
cout << ma;
}
return 0;
}
```
noice
Created at
10 likes
zxcvbnm0123toi
Created at
1 likes