高效算法——M 扫描法

In an open credit system, the students can choose any course they like, but there is a problem. Some of the students are more senior than other students. The professor of such a course has found quite a number of such students who came from senior classes (as if they came to attend the pre requisite course after passing an advanced course). But he wants to do justice to the new students. So, he is going to take a placement test (basically an IQ test) to assess the level of difference among the students. He wants to know the maximum amount of score that a senior student gets more than any junior student.

For example, if a senior student gets 80 and a junior student gets 70, then this amount is 10. Be careful that we don’t want the absolute value. Help the professor to figure out a solution. Input Input consists of a number of test cases T (less than 20).

Each case starts with an integer n which is the number of students in the course. This value can be as large as 100,000 and as low as 2. Next n lines contain n integers where the i’th integer is the score of the i’th student. All these integers have absolute values less than 150000. If i < j, then i’th student is senior to the j’th student.

Output

For each test case, output the desired number in a new line. Follow the format shown in

sample

input-output section.

Sample Input

100

Sample Output

-1

解题思路：

这个题目的意思是n个数组成一个序列，求两数最大的差，PS：这个序列不能改变原数的位置，即要从前面第一个数开始与后面每一个数作差，但是是这样时间可能会超时，所以我们每找一个数，与之前的最大数作差后，再与之前最大差相比，存下最大差；然后再与它之前的那个最大数相比，存下最大数，循环下去，只要循环n-1次即可。

程序代码：

#include <cstdio>
using namespace std;
int max(int a,int b)
{
    return a>b?a:b;
}
int a[200005];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
       scanf("%d",&n);
       for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
       int ans=-1;
       int f=a[0];
       for(int i=1;i<n;i++)
       {
        ans=max(ans,f-a[i]);
        f=max(f,a[i]);
       }
       printf("%d
",ans);
    }
    return 0;
}

View Code