【水题】求条件最大值

求条件最大值

Time Limit: 1000MS Memory limit: 65536K

题目描述

懒得想背景故事了，开门见山。

有一个长度为n的整数数列A0,A1,A2....An-1。从中找出两个整数Ai和Aj,Ai在Aj的前面，即i<j，使得Ai-Aj尽可能的大。请输出可能的最大的Ai-Aj的值。

输入

 多组输入。每一组测试数据的第一行是一个整数n，然后第二行是n个整数，第i个数

表示Ai。（测试数据组数<=20，2<=n<=10^6,-10^8<=Ai<=10^8）.

输出

 每组测试数据输出一行一个整数，为可能的最大的Ai-Aj的值。

示例输入

5
3 1 2 4 3
5
3 1 2 4 1

示例输出

2
3

应该从后开始求最小值，当从后开始只有1个数的时候，最小值就是本身；当从后开始只有2个数的时候，应该是两个数中的最小值；当从后开始只有3个数的时候，
最小值为3个数中的最小值......当从后开始数n个数的时候，最小值为n个数中的最小值，先把这个求出来，然后再遍历比较就可以了。

#include<iostream>  
#include<algorithm>  
#include<stdio.h>  
  
  
using namespace std;  
  
int s[1000100], t[1000100];  
int maxx, minn;  
  
int main()  
{  
    int n, i,  k=1, maxx, minn;  
    while(cin>>n)  
    {  
        k =1;  
        minn = 1e9;  
        maxx = -1e9;  
        for(i=0; i<n; i++)  
            scanf("%d", &s[i]);  
        minn = s[n-1];  
        t[k++] = minn;  
        for(i=n-2; i>=1; i--)//求最小值
        {  
            if(s[i]<minn)  
            {  
                t[k++] = s[i];  
                minn = s[i];  
            }  
            else  
            {  
                t[k++] = minn;  
            }  
  
        }  
      
        for(i=0; i<n-1; i++)  
        {  
            if( (s[i]-t[n-i-1]) >maxx)  
            {  
                maxx = s[i]-t[n-i-1];  
            }  
        }  
        printf("%d\n", maxx);  
    }  
    return 0;  
}