洛谷 P5146 最大差值 C语言

P5146 最大差值 - 洛谷 | 计算机科学教育新生态

题目描述

HKE 最近热衷于研究序列，有一次他发现了一个有趣的问题：
对于一个序列 A1​,A2​,…,An​，找出两个数 i,j（1≤i<j≤n），使得 Aj​−Ai​ 最大。
现在给出这个序列，请找出 Aj​−Ai​ 的最大值。

输入格式

第一行为一个正整数 n。
接下来 n 行，每行一个整数，第 (i+1) 行的整数为 Ai​。

输出格式

一行，为 Aj​−Ai​ 的最大值。

输入输出样例

输入 #1

10
1
3
4
6
7
9
10
1
2
9

输出 #1

9

说明/提示

数据规模与约定

• 对于 30% 的数据，n≤1000；
• 对于 70% 的数据，n≤1e5；
• 对于 100% 的数据：2≤n≤1e6，Ai​ 在 int 范围内。

思路如下：
 

一开始肯定有很多审题不认真的小伙伴，用排序或者变量跟踪最大值和最小值求解答，发现才58分。

这是因为，这题是先确定i,j。i<=j 再确定a[j]-a[i]。假设是10 2 3.下标是1 2 3 。本来i < j -> 1 < 3.sort之后10排在2后面去了。所以不满足条件。这题不能排序

那么解题思路如下：

暴力思路就是O(n*n):

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N = 1e6+10;
ll n;
ll arr[N];
int main() 
{
	ll ans = -1e10;
	cin >> n;
	for(ll i = 1 ; i <= n ; i++)
	cin >> arr[i];
	for(ll i = 1 ; i <= n ; i++)
	{
		for(ll j = 1 ; j <= n ; j++)
		{
			if(arr[j] - arr[i] > ans && j > i)
			ans = arr[j] - arr[i];
		}
	}
	cout << ans;
	return 0;
}

优化：

用递推思路，使用ans变量跟踪区间最大值，因为j > i ,所以再用一个变量跟踪最小值。其实就是滑动串口。也是贪心。当输入一个最小值比当前最小值还要小的时候，窗口就从这个最小值开始了，因为j > i.

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll n;
ll ans = -1e10;
int main() 
{
	cin >> n;
	ll curmin;
	cin >> curmin;
	for(ll i = 2 ; i <= n ; i++)
	{
		ll t;
		cin >> t;
		if(t - curmin > ans)
		ans = t - curmin;
		if(t < curmin)
		curmin = t;
	}
	cout << ans;
	return 0;
}