3.30 阿里校招实习笔试
第一题 超时了……
第二题 有n个数，其找出其子集，满足：
是连续的自然数，如集合[1 2 3]
1 2 3 12 23 123 都是，13就不是，求每个子集最大值的期望
（我最后才反应过来他给的数据不一定是连续的，所以要判断子集是否合法 等我改完已经交卷了…… ）
（awsl 吃了两个鸭蛋）
#n 个数的子集和最大值的期望
#连续的子序列
def valid(arr):
if len(arr)==1:
return True
else:
for i in range(len(arr)-1):
if arr[i+1]-arr[i]!=1:
return False
return True
def get_vec(n):
#已排好序的
res=[]
dicta={}
for i in range(1,len(n)+1):
for j in range(0,len(n)):
temp=n[j:j+i]
if temp not in res and valid(temp)==True:
res.append(temp)
for i in res:
maxnum=max(i)
if maxnum not in dicta:
dicta[maxnum]=1
else:
dicta[maxnum]+=1
lenres=len(res)
res=0
for i in dicta.keys():
res+=float(i/lenres)*i
return res
def test():
n=int(input())
lst=input().split(' ')
newlst=[]
for i in lst:
newlst.append(int(i))
ans='%.6f'%get_vec(newlst)
return ans
print(test())
