算法-每天一道题（9）-最大间隔

题目描述

给定一个递增序列，a1 <a2 <...<an 。定义这个序列的最大间隔为d=max{ai+1 - ai }(1≤i<n),
现在要从a2 ,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少？

输入描述:
第一行，一个正整数n(1<=n<=100),序列长度;接下来n个小于1000的正整数，表示一个递增序列。

输出描述:
输出答案。

输入例子:
5
1 2 3 7 8

输出例子:
4

C++

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int n;
    while(cin >> n)
    {
        vector<int> array(n);
        for (int i=0; i<n; i++)
            cin >> array[i];
 
        int old_max = 0;
        int new_max = 999; // 表示无限大
        int temp = 0;
        // 取出没有删除之前的最大间隔
        for (int i=1; i<n; i++)
        {
            temp = array[i] - array[i-1];
            if (old_max < temp)
                old_max = temp;
        }
 
        // 删除之后的最大间隔
        for (int i=2; i<n; i++)
        {
            temp = array[i] - array[i-2];
            // 如果删除之后的间隔小于删除之前的最大间隔，
            // 表明删除不会影响最大间隔，所以最大间隔不变
            if (temp < old_max)
            {
                new_max = old_max;
                break;
            }
            else 
                // 将每次删除且会影响old_max的间隔保存起来
                // 与之前的影响old_max的间隔比较，取小值
                if (temp < new_max)
                    new_max = temp;
        }
        cout << new_max << endl;
    }
    return 0;
}

/*
解题思路：
刚才有道题没有保存成功，没有了..[泪]

如果删除之后，间隔比之前的最大间隔小，
说明删除不会影响最大间隔，即返回old_max

删除之后的间隔比最大间隔大，则取小值
*/