Hướng dẫn giải của Khuyến mãi đặc biệt
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Nhận xét: giá trị của ~f(l, r) \ge f(l, r+1)~ ~(1 \le l < r < n)~.
Thật vậy, giả sử ~V_r = min(a_l, a_{l+1}, ..., a_r)~ thì ~V_{r+1} = min(a_l, a_{l+1}, ..., a_{r+1}) = min(V, a_{r+1})~. Ta thấy nếu ~a_{r+1} \ge V_r~ thì giá trị ~V_{r+1} = V_r~. Ngược lại, nếu ~a_{r+1} < V_r~ thì ~V_{r+1} = a_{r+1} < V_r~. Điều này cho ta thấy việc mở rộng đoạn con đang xét ra sẽ không làm cho kết quả tốt hơn.
Từ đây, ta thấy đáp án tốt nhất sẽ nằm trong các giá trị ~f(1, 2), f(2, 3), ..., f(n-1, n)~. Ta tìm ~max~ của các giá trị này sẽ ra được kết quả.
Code tham khảo:
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;
/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
bool maximize(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
/***End of Template***/
int n;
const int N = 1e5+5;
int a[N];
void Input() {
cin >> n;
FOR(i, 1, n) cin >> a[i];
}
void Solve() {
ll ans = 0;
FOR(i, 1, n-1) ans = max(ans, 1ll*a[i]*a[i+1]);
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--)
Input(), Solve();
return 0;
}
Bình luận