PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter:Jeevan Jyot Singh
Tester: Abhinav Sharma
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Easy-Medium
PREREQUISITES:
PROBLEM:
Given a sequence X of length M, f(X) is defined as f(X) = \sum_{i = 1}^{M - 1} |X_{i + 1} - X_i|.
JJ has an array A of length N. He wants to divide the array A into two subsequences P and Q (possibly empty) such that the value of f(P) + f(Q) is as large as possible. (Note that each A_i must belong to either subsequence P or subsequence Q).
Help him find this maximum value of f(P) + f(Q).
EXPLANATION:
We follow 1-based array indexing for this solution.
Let dp[i][j] denote the maximum value of f(P) + f(Q) such that:
- All the elements till index max(i, j) have been divided into subsequence P and Q
- Subsequence P ends at the i^{th} element and subsequence Q ends at the j^{th} element.
Note that, since the elements at indices i and j lie in different subsequences, i \neq j.
The first element which has not been added to any of the subsequences yet is the element at position k = max(i,j) +1.
While adding the k^{th} element to subsequence P, two cases are possible:
- i>0: The last element added to subsequence P was the i^{th} element of the array. Thus, on adding the k^{th} element to subsequence P, we add abs(A[k]-A[i]) to f(P). Formally, dp[k][j] = max(dp[k][j], dp[i][j] + abs(A[k]- A[i])).
-
i = 0: This means that no element was added to subsequence P yet. The first element added to subsequence P is the k^{th} element of the array.
Thus, dp[k][j] = max(dp[k][j], dp[i][j] + 0).
Similarly, if we add the k^{th} element to subsequence Q, two cases are possible:
- j>0: The last element added to subsequence Q was the j^{th} element of the array. Thus, on adding the k^{th} element to subsequence Q, we add abs(A[k]-A[j]) to f(Q). Formally, dp[i][k] = max(dp[i][k], dp[i][j] + abs(A[k]- A[j])).
-
j = 0: This means that no element was added to subsequence Q yet. The first element added to subsequence Q is the k^{th} element of the array.
Thus, dp[i][k] = max(dp[i][k], dp[i][j] + 0).
The final answer would be the maximum out of all dp[i][j].
TIME COMPLEXITY:
The time complexity is O(N^2) per test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
const long long INF = 1e18;
const int N = 1e6 + 5;
void solve()
{
int n; cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++)
cin >> a[i];
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
int ans = 0;
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n; j++)
{
ans = max(ans, dp[i][j]);
int to = max(i, j) + 1;
if(i == j or to > n) continue;
dp[to][j] = max(dp[to][j], dp[i][j] + (i == 0 ? 0 : abs(a[to] - a[i])));
dp[i][to] = max(dp[i][to], dp[i][j] + (j == 0 ? 0 : abs(a[to] - a[j])));
}
}
cout << ans << endl;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
while(T--)
solve();
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
cin >> T;
while(T--){
int n;
cin>>n;
int a[n];
rep(i,n){
cin>>a[i];
}
vector<vector<int> > dp(n+1, vector<int>(n+1,0));
//dp[i][j] represents maximum ans if the two sequences end at i and j
int ans = 0;
rep(i,n+1){
rep_a(j,i+1,n){
dp[i][j+1] = max(dp[i][j+1],dp[i][j]+abs(a[j]-a[j-1]));
dp[j][j+1] = max(dp[j][j+1],dp[i][j]+(i==0?0:abs(a[j]-a[i-1])));
ans = max(ans, max(dp[i][j+1], dp[j][j+1]));
}
}
cout<<ans<<'\n';
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n+1];
for(int i = 1; i<=n; i++){
cin>>a[i];
}
int ans = 0;
int dp[n+1][n+1];
memset(dp, 0, sizeof(dp));
for(int i = 0; i<=n; i++){
for(int j = 0; j<=n; j++){
int k = max(i, j) + 1;
if(i==j || k>n) continue;
if(i==0) dp[k][j] = max(dp[k][j], dp[i][j]);
else dp[k][j] = max(dp[k][j], dp[i][j] + abs(a[k]-a[i]));
if(j==0) dp[i][k] = max(dp[i][k], dp[i][j]);
else dp[i][k] = max(dp[i][k], dp[i][j] + abs(a[k]-a[j]));
ans = max({ans, dp[k][j], dp[i][k]});
}
}
cout<<ans<<endl;
}
return 0;
}
