题意
给出一个整数组成的序列，求两个整数A和B，其中A在数列的位置在B前面，令A-B最大，输出这个最大值。
思路
利用问题的单调性优化的典型例子。
暴力是O(n^2)的，显然无法通过。注意到A始终在B的前面，而且一定是A-B，也就是说对于每一个B，只要找到在它前面最大的A就可以了，不妨考虑随着B逐渐后移的同时，维护前面A的最大值，这样做的复杂度是O(n)的，很完美地解决了这个问题。
这种思想经常会被用在其他问题中作为一个需要优化的环节。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXN = 100005; int n,seq[MAXN]; int main(){ int caseCnt; scanf(" %d",&caseCnt); for(int d = 1; d <= caseCnt; d++){ scanf(" %d",&n); for(int i = 1; i <= n; i++){ scanf(" %d",&seq[i]); } int res = 0x80000000; int mx = seq[1]; for(int i = 2; i<= n; i++){ res = max(res,mx-seq[i]); mx = max(mx,seq[i]); } printf("%d\n",res); } return 0; } |
