大意:找出两个整数Ai和Aj,使得Ai-Aj尽量大。
思路:最直接是两重暴力,或者维护j相等时(1<=j-1)的最大Ai,记录路径可以添加三个指针即可。
#include <iostream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <stack> #include <algorithm> #include <cctype> using namespace std; const int maxn = 100010; int A[maxn]; int n; void read_case() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &A[i]); } void solve() //输出路径 { read_case(); int Si = 0, Si2 = 0, Sj = 1; int ans = A[0]-A[1]; int MaxAi = A[0]; for(int j = 1; j < n; j++) { if(ans < MaxAi-A[j]) { ans = MaxAi-A[j]; //Si2 = Si; //Sj = j; } if(MaxAi < A[j]) { MaxAi = A[j]; //Si = j; } } //printf("%d %d %d\n", ans, Si2, Sj); printf("%d\n", ans); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }