1.题目描述:点击打开链接
2.解题思路:本题一看n的范围高达100000,肯定只能用O(N)的复杂度解决。本题类似于最大连续和问题,事先计算区间[0,i)的最大值,存放到_max数组中,然后扫描整个数组,不断用max(ans,_max[i]-a[i])更新最大差值即可。本题附上利用O(1)更新MaxAi来计算最大值的程序。更新顺序值得学习!
3.代码:
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<string> #include<sstream> #include<set> #include<vector> #include<stack> #include<map> #include<queue> #include<deque> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<functional> using namespace std; #define N 100000+10 #define INF 150000+10 int a[N]; int _max[N]; void init() { for (int i = 0; i < N; i++) _max[i] = -INF; } int main() { //freopen("t.txt", "r", stdin); int T; cin >> T; while (T--) { init(); int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) _max[i] = max(_max[i - 1], a[i - 1]); int ans = -2 * INF; for (int i = 1; i < n; i++) ans = max(ans, _max[i] - a[i]); printf("%d\n", ans); } return 0; }
参考程序:
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<string> #include<sstream> #include<set> #include<vector> #include<stack> #include<map> #include<queue> #include<deque> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<functional> using namespace std; #define N 100000 int a[N], n; int main() { //freopen("t.txt", "r", stdin); int T; cin >> T; while (T--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", a + i); int ans = a[0] - a[1]; int MaxAi = a[0]; for (int j = 1; j < n; j++) { ans = max(ans, MaxAi - a[j]); MaxAi = max(a[j], MaxAi);//MaxAi晚于ans更新,因为更新ans时候MaxAi不包括第j个数 } printf("%d\n", ans); } return 0; }