最大间隔

[编程题]最大间隔

热度指数：12096 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

输出描述:

输出答案。

示例1

输入

5
1 2 3 7 8

输出

算法知识视频讲解

Python

离疏

while 1:
    try:
        n=int(input())
        a=list(map(int,input().split()))
        origin_max,res_min=0,1000
        for i in range(1,n):#计算原始最大间隔
            d=a[i]-a[i-1]
            if d>origin_max:
                origin_max=d
        for i in range(2,n):#计算剩余序列的最小间隔
            d=a[i]-a[i-2]
            if d<res_min:
                res_min=d
        print(max(origin_max,res_min))#返回较大者
    except:
        break

发表于 2018-08-02 16:41:13 回复(0)

Python

华科平凡

python解法如下：
gaps是两个相临数之间的差的列表
delgaps是删除一个数后，相临两个数之间的差的列表。
如果gaps中最大数大于等于delgaps中最小的数，直接返回该数。
否则返回delgaps中最小的数。

while True:
    try:
        a,b=input(),list(map(int,input().split()))
        gaps,delGaps=[],[]
        for i in range(1,len(b)):
            gaps.append(b[i]-b[i-1])
        for i in range(1,len(gaps)):
            delGaps.append(gaps[i]+gaps[i-1])
        print(max(gaps) if max(gaps)>=min(delGaps) else min(delGaps))
    except:
        break

发表于 2017-09-16 09:57:25 回复(0)