首页 > itarticle > open credit system – uva 11078

open credit system – uva 11078

admin 11月 12, 2020 0

Problem

Summary

Given a list A, find the max(a[i]-a[j]) with i < j.

Analyse

max(a[i]-a[j]) = max(max(a[1..j-1]) - a[j]).
Complexity: O(n).

Code in C++

#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 1000000000;
int T;
int n;
int MAX, x, ans;
int () {
	cin >> T;
	while (T--) {
		cin >> n;
		cin >> MAX;
		ans = -INF;
		for (int i = 1; i < n; i++){
			cin >> x;
			if (MAX - x > ans)
				ans = MAX - x;
			if (x > MAX)
				MAX = x ;
		}
		cout << ans << endl;
	}
	return 0;
}