0
0
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
2901
1827
Để giải bài toán này, ta có thể dùng phương pháp quy hoạch động đoạn con với độ phức tạp O(n).
Do có t test case, vậy độ phức tạp của chương trình là O(tn).
$\\$
$\text{Code tham khảo:}$
#include <iostream>
#include <algorithm>
#define N 1005
using namespace std;
int t, n, a[N], f[N];
int main() {
freopen("BS.INP", "r", stdin);
freopen("BS.OUT", "w", stdout);
cin >> t;
while (t--) {
cin >> n;
for (int i=1; i<=n; ++i) cin >> a[i];
fill(f+1, f+n+1, 0);
f[1] = a[1]^1;
for (int i=2; i<=n; ++i) {
if (a[i] == 0) f[i] = f[i-1] + 1;
}
cout << *max_element(f+1, f+n+1) << endl;
}
}
$\\$
$\\$
$\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}$
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin