Maximum difference between A[j] and A[i] such that j < i and A[j] < A[i]

max_diff_brute_force.cpp

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

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int& a : A) {
            cin >> a;
        }
        int max_diff = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                max_diff = max(max_diff, A[i] - A[j]);
            } 
        }
        cout << max_diff << "\n";
    }
    return 0;
}

max_diff_linear.cpp

/* Copyright 2015 Rafael Rendón Pablo <[email protected]> */
// region Template
#include <bits/stdc++.h>
using namespace std;
typedef long long           int64;
typedef unsigned long long  uint64;
const double kEps   = 10e-8;
const int kMax      = 1000;
const int kInf      = 1 << 28;
// endregion

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int& a : A) {
            cin >> a;
        }
        int max_diff = 0;
        int min_val = A[0];
        for (int i = 1; i < n; i++) {
            max_diff = max(max_diff, A[i] - min_val);
            min_val = min(min_val, A[i]);
        }
        cout << max_diff << "\n";
    }
    return EXIT_SUCCESS;
}

max_diff_test_gen.rb

tests = 100
max_n = 5000
max_v = 15485863
puts tests
1.upto(tests) do
  n = rand(max_n)
  print "#{n} "
  1.upto(n) do
    v = rand(max_v)
    v = -v if rand(2) == 0
    print "#{v} "
  end
  puts
end