Yêu cầu: Tìm giá trị lớn nhất của biểu thức a_j - a_i  (1<=i<j<=n)

Dữ liệu:

• - Dòng đầu tiên chứa số nguyên n (0<n<=10⁶)

• - Dòng thứ 2 là các số nguyên (0<a_i<=10⁶)  a₁, a₂, ..., a_n    (0<a_i<=10⁶)

Kết quả:

• Một dòng duy nhất ghi giá trị lớn nhất của biểu thức.

Ví dụ

• Input7
  8 2 4 -2 9 1 -3
• Output
• 11
• (C++ nhe)

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

int n, a[N] ;
int mi[N], ma[N] ;
int main ()
{
    cin >> n ;
    
    mi[0] = N ; // tim GTNN ben phai ke tu phan tu a[i]
    for (int i=1; i<=n; i++)
    {
        cin >> a[i] ;
        mi[i] = min (mi[i-1], a[i]) ;
    }
    
    ma[n] = a[n] ; // tim GTLN ben trai phan tu a[i]
    int b = 0 ;
    for (int i=n-1; i>=1; i--)
    {
        ma[i] = max (ma[i+1], a[i]) ;
        b = max (b, ma[i+1]-mi[i] ) ; // khoang cach lon nhat 
    }
    
    cout << b ;
    return 0 ;
}

Đáp án:

/**
 *    author:  tđq
**/
#include <bits/stdc++.h>
#define task ""

using namespace std;

typedef long long ll;

const ll nmax = 1e5 + 5;

ll a[nmax], dp[nmax], n, mx = 0;
int main()
{

 //freopen(task".inp" , "r" , stdin);
 //freopen(task".out" , "w" , stdout);

 ios::sync_with_stdio(false);
 cin.tie(0);
 
 cin >> n;
 for (ll i = 1; i <= n; ++i)
 {
   cin >> a[i];
   dp[i] = min(dp[i - 1], a[i]);
 }
 for (ll i = 2; i <= n; ++i)
 {
   mx = max(mx , a[i] - dp[i - 1]);
 }
 cout << mx;
 return 0; 
}

Giải thích các bước giải: