```c++

```

We have to maximize $$$ \left( {A_i - A_j} \right) \times A_k $$$. So for every index $$$j$$$ from $$$2$$$ to $$$n-1$$$, we have to find the maximum element $$$A_i$$$ from the left side $$$(1 \le i \lt j)$$$ and the maximum element $$$A_k$$$ $$$(j \lt k \le n)$$$ from the right side. Which can be done using prefix_max and suffix_max. Then we will traverse the array from $$$2$$$ to $$$n-1$$$ and our answer will be max(answer, ($$$pref_max[j-1]$$$-$$$A[j]$$$)*$$$suffix_max[j+1]$$$).

If final answer is negative, then we will output 0.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define f(i, x, n) for (ll i = x; i < n; i++)
#define rf(i, x, n) for (ll i = x; i >= n; i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
const ll p = 1e9 + 7;
const ll inf = 1e18;
const ll N = 1e4+5;

void solve() {
    ll n;
    cin>>n;
    vector<ll> a(n);
    f(i,0,n) cin>>a[i];
    vector<ll> pref(n), suf(n);
    f(i,0,n) {
        pref[i]=max(i==0?a[0]:pref[i-1],a[i]);
    }
    rf(i,n-1,0) {
        suf[i]=max(i==n-1?a[i]:suf[i+1],a[i]);
    }
    ll ans=-inf;
    f(i,1,n-1) {
        ans=max(ans,(pref[i-1]-a[i])*suf[i+1]);
    }
    if(ans<0) ans=0;
    cout<<ans<<'\n';
}   

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    cin >> t;
    for (ll T = 1; T <= t; T++) {
        // cout << "Case " << T << ": ";
        solve();
    }  
    return 0;
}

Lets take a sequence $$$...U_1OU_2...$$$, where $$$U_1$$$,$$$U_2$$$ are segments of unowned lands and $$$O$$$ is segment of owned lands. Then you can give $$$O$$$ and take whole segment $$$U_1OU_2$$$, here you can see overall you have taken $$$U_1$$$ and $$$U_2$$$. So you can take any two consecutive segments of unowned lands and we can maximize it in $$$O(N)$$$ by just brute forcing on string.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    vector<int> lenOfZeroSeg;
    int ans=0;
    for(int i=0;i<n;){
        if(str[i]=='1'){ans++;i++;continue;}
        int cnt=0;
        while(i<n && str[i]=='0'){
            i++;
            cnt++;
        }
        if(cnt!=0)lenOfZeroSeg.push_back(cnt);
    }
    // cout<<lenOfZeroSeg.size()<<endl;
    int mx=0;
    for(int i=0;i<((int)lenOfZeroSeg.size())-1;i++){
        mx=max(mx,lenOfZeroSeg[i]+lenOfZeroSeg[i+1]);
    }
    ans+=mx;
    cout<<ans<<endl;
    return 0;
}

Here durability simply means number of edges between any nodes, and it breaks on traveling. And we will solve this question for all its component individually, because it anyways takes $$$1$$$ air-travel to move between connected components.

For any connected component, we have two types of nodes: even degree nodes and odd degree nodes.

EVEN DEGREE: When we will air-travel on even degree and break all edges connected to it, we will end up on that node only, so we have to use air travel to go on any other node.

ODD DEGREE: When we will air travel on odd degree and break all edges connected to it, we will end up in some other node than this, and if that is even degree node then by coming in that edge it becomes odd degree(because we have broke one edge and came on that) and this is again case of ODD DEGREE. If we go to any odd degree then it will become even and as we have seen upward we will end up on that node only after breaking all edge, so we have to use air-travel to go to other nodes.

So optimal strategy is to go from one odd degree node to another odd degree node and take all other even degree node on the way. So this will require air-travel equal to half the number of odd degree vertices. If all edges are even we can see, any even degree node as two odd degree nodes and make $$$1$$$ air travel and remove all edges in that component. If any component don't have any edge then no need to air-travel on it.

If you have understood logic then implementation is very easy.

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+1;
vector<int> edge[N];
bool vis[N];
int deg[N];
int cnt=0;
int dfs(int ind){
    cnt++;
    int ans=(deg[ind]%2);
    vis[ind]=1;
    for(auto child:edge[ind]){
        if(!vis[child])ans+=dfs(child);
    }
    return ans;
}

int main(){
    int tc;
    cin>>tc;
    while(tc--){
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++){
            vis[i]=0;
            deg[i]=0;
            edge[i].clear();
        }
        for(int i=0;i<m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            edge[u-1].push_back(v-1);
            edge[v-1].push_back(u-1);
            deg[u-1]+=(w%2);
            deg[v-1]+=(w%2);
        }
        int ans=0;
        for(int i=0;i<n;i++){
            if(!vis[i]){
                cnt=0;
                int curans=dfs(i);
                if(curans==0 && cnt!=1)ans++;
                else ans+=(curans/2);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

In this question, first thing to observe is for all continuous three stones $$$i,j$$$ and $$$k$$$, $$$dist(j,k) \gt x-dist(i,j)$$$ and $$$dist(j,k) \le x$$$.

So here we have some constrains on putting stones, i.e we have to put at least $$$1$$$ real stone in following $$$y(y \le x)$$$ stones. Now we can think of DP solution here, having 2-D dp, $$$dp_{i,j}$$$ denoting number of ways to put real stones in total $$$i$$$ stones and with the initial constrain as $$$j$$$. Here constrain $$$j$$$ denotes that first $$$j$$$ stones after $$$1_{st}$$$ stones can't be real.

So for computing $$$dp_{i,j}$$$ our formula will be:

Now because you are reading editorial of this question, it should be easy task to implement it.

#include <bits/stdc++.h>
using namespace std;
 
long long int MOD=1e9+7;
const int N=1e3+1;
int n,x;
long long int dp[N][N];
int func(int stn,int con){
    if(con>=x)return 0;
    if(stn<0){
        return 1;
    }
    if(dp[stn][con]!=-1)return dp[stn][con];
    dp[stn][con]=0;
 
 
    //In O(N^3) loop runs from con to x for all con, but to get it in we will use dp[stn][con+1] and add remaining thing.
    //This is for O(N^2).
    dp[stn][con]=func(stn,con+1);
    if(stn-con-1>=0 || con==x-1)dp[stn][con]+=func(stn-con-1,x-con-1);
    dp[stn][con]%=MOD;
    
    //This is for O(N^3).
    // for(int i=con;i<x;i++){
    //     dp[stn][con]+=func(stn-i-1,x-i-1);
    //     if(stn-i-1<0)break;
    // }
    return dp[stn][con];
}
 
 
int main(){
    cin>>n;
    cin>>x;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dp[i][j]=-1;
        }
    }
    cout<<func(n-1,0)<<endl;
    return 0;
}