Bài tập c++ về order statistics

[giang3 (Giang11)]

Cho mảng a gồm n số nguyên. Hãy tìm hiệu lớn nhất của bất kể hai phần tử nào của mảng dãy con thỏa mãn số lớn hơn xuất hiện sau số nhỏ hơn. Nếu không tìm được cặp phần tử nào hãy đưa ra giá trị -1.

Input	Ouput
3 3 2 1	-1
7 2 3 10 6 4 8 1	8

Dưới là code của em.
Em đang k biết cách nào để đưa ra trường hợp -1. Và cho em hỏi là cách của em có ra được với bộ test 1<=n<=10^5 và 1<=a[i]<=10^5 không ạ? Anh chị giúp em với ạ. Em cám ơn.

#include<iostream>
using namespace std;
int main() {
	int t;
	cin>>t;
	while(t--) {
		int n,*a;
		cin>>n;
		a=new int[n+1];
		for(int i=1;i<=n;i++) {
			cin>>a[i];
		}
		int res=INT_MIN;
		for(int i=1;i<n;i++) {
			for(int j=i+1;j<=n;j++) {
				if (a[j] > a[i]) {
					int h=a[j] - a[i];
					res=max(res,h);
				}
			}
		}
		cout<<res;
	}
}

[giang3 (Giang11)]

Cách gì vậy anh.em mới học còn ngơ quá.

[Tan_Kiem (NKTan)]

Đây là cách của mình O(N) cách của bạn O(N^2) thì sẽ bị quá thời gian với test case kia:

Int res=INT_MIN,Min=a[0];
for(int i=1;i<n;i++){
       res=max(res,a[i]-Min);
       Min=min(Min,a[i]);
}
if(res<=0) cout<<-1;
else cout<<res;

[rogp10]

tự facepalm nhầm qua bài số bé đứng trước số lớn (khó hơn) như trên là đúng rồi.

[giang3 (Giang11)]

anh ơi làm cách nào để biết thời gian là O(N^2) được ạ

[rogp10]

Quy tắc nhân có thể phát biểu: Một công việc T có độ phức tạp O(f) được thực hiện O(g) lần sẽ có độ phức tạp là O(f(n)*g(n)).

[giang3 (Giang11)]

nếu nhìn bộ test ở bài em thì biết độ phức tạp bao nhiêu là phù hợp và có thể run được ạ

[rogp10]

Thay số vào độ phức tạp bạn nếu 10^9 thì tùy bài nhưng 10^10 thì chắc chắn là không được.