鱼C论坛Python精英挑战赛（第四季01期）

jerryxjr1220

第四届鱼C论坛精英挑战赛即将回归咯！为了增加趣味性，本届仍然延续“新玩法”-- “押宝玩法”，“竞猜玩法”和“擂主玩法”。

同时，根据以往鱼油的反馈，精英赛题目普遍偏难，所以参与的鱼油相对较少。为了提高大家的参与度，本届挑战赛会大幅降低难度，使大部分鱼油都能参赛。同时，会增设一、二、三名奖励，第一名奖励50鱼币，第二名30鱼币，第三名20鱼币。

新玩法规则：

1. 押宝玩法：进入“押宝”竞猜帖，购买主题（5鱼币）参与“押宝”，最终“押宝”获胜者将平分奖池的奖金并额外获取10鱼币奖励。猜错者将不返还“押宝”的鱼币。若本届比赛无人“押宝”成功，奖金将累计到下次比赛。

2. 竞猜玩法：直接在比赛帖的下方进行投票，凡事“竞赛”获胜者，将奖励5鱼币。竞猜无门槛，人人都可以参与。竞猜以后，请在本帖留个言，方便领取奖励。

3. 擂主玩法：上一期挑战成功的鱼油成为挑战赛的擂主，擂主有优先权提议下一期的赛题，一届挑战赛共分5期，同一届中当擂主最长的鱼油有额外奖励。

本期题目： 最大包含的水的面积

给定一个包含若干数值的列表，例如：[1,8,6,2,5,4,8,3,7]，其中每个数值代表一个木板的长度，在任意两个木板间注水，可以得到其包含的注水面积，如下图蓝色部分的面积为8x5=40（8是木板长度，5是两木板间隔的距离）


这2块木板见的水面积是这样的。


求给定列表中两木板间包含的最大的水的面积。

1. def max_area(list_of_number):
   
2.     '''your code here'''
   
3.     return result_of_max_area

复制代码

要求： 结果正确，程序效率高，代码简洁

注：给定的列表长度可能会达到1000或以上，请注意运算效率

看到不少鱼油已经非常快得都递交了答案，这个单从难度来说还是比较简单的，不过对于超长列表来说，运算效率是一大问题。比如说给个100万长度的列表，你的程序算得出来吗？

截止日期： 11月30日0时

本期擂主： 蓝色王魂  由于本期只有算法题，所以就不给选择了

@小甲鱼 @冬雪雪冬 @～风介～ @SixPy

竞猜：回答正确的参赛者的人数

冬雪雪冬

第二和第十之间怎么算？
这样


还是这样

BngThea

1. def max_area(lst):
   
2.     length = len(lst)
   
3.     area = []
   
4.     for i in range(length - 1):
   
5.         temp = []
   
6.         for j in range(i + 1,length):
   
7.             temp.append((j - i) * (lst[i] if lst[i] < lst[j] else lst[j]))            
   
8.         area.append(max(temp))
   
9.     return max(area)
   
10. 
    
11. 
    
12. lst = [1,8,6,2,5,4,8,3,7]
    
13. print(max_area(lst))

复制代码

yjsx86

1. L = [1, 8, 6, 2, 5, 4, 8, 3, 7]
   
2. 
   
3. def max_area(_list):
   
4.     rs = []
   
5.     for i in range(len(_list)):
   
6.         for j in range(i, len(_list)):
   
7.             rs.append((_list[i] if _list[i] < _list[j] else _list[j]) * abs(i - j))
   
8.     return max(rs)
   
9. 
   
10. print(max_area(L))

复制代码

aegis1417

試試水溫

1. def max_area(list_of_num):
   
2.         from itertools import combinations
   
3.         b=[i for i in range(len(list_of_num))]
   
4.         a=list(combinations(b, 2))
   
5.         d=[]
   
6.         for i in a:
   
7.                 if list_of_num[i[0]]>list_of_num[i[1]]:
   
8.                         d.append(list_of_num[i[1]]*(i[1]-i[0]))
   
9.                 else:
   
10.                         d.append(list_of_num[i[0]]*(i[1]-i[0]))
    
11.         return print(max(d))
    
12. 
    
13. max_area([1,8,6,2,5,4,8,3,7])

复制代码

蓝色王魂

1. def max_area(list_of_number):
   
2.     length = len(list_of_number)
   
3.     result_of_max_area = 0
   
4.     for i in range(length):
   
5.         for j in range(i+1,length):
   
6.             area = (j - i)*(min(list_of_number[i], list_of_number[j]))
   
7.             if area > result_of_max_area:
   
8.                 result_of_max_area = area
   
9.     return result_of_max_area

复制代码

SixPy

1. import numpy as np
   
2. def max_area(ls):
   
3.     a = np.array(ls)
   
4.     x,y = np.triu_indices(len(ls),1)
   
5.     return (np.where(a[x]<a[y],a[x],a[y])*(y-x)).max()
   
6. 
   
7. ls = [1,8,6,2,5,4,8,3,7]
   
8. print(max_area(ls))
   
9. #49

复制代码

SixPy

@jerryxjr1220 支持大内存，要用64位的python和numpy

一片模糊望尘世

1. def max_area(nums):
   
2.     l = 0
   
3.     r = len(nums) - 1
   
4.     area = 0
   
5.     for width in range(len(nums) - 1, 1, -1):
   
6.         height = min(nums[l], nums[r])
   
7.         area = max(area, height * width)
   
8.         if nums[l] > nums[r]:
   
9.             r -= 1
   
10.         else:
    
11.             l += 1
    
12. 
    
13.     return area
    

复制代码

梦想绘制者

感觉题目有问题呢。例子中的最大面积应该是在第1块与第9块之间注水得到的1+8×5+7×2 = 55吧？

Elastcio

1. def max_area(o_list):
   
2. 
   
3.     import numpy as np
   
4. 
   
5.     #o_list = [1,8,6,2,5,4,8,3,7]
   
6. 
   
7.     length = len(o_list)
   
8.     mat1 = np.mat(np.zeros((length,length)))
   
9. 
   
10.     for i in range(length):
    
11.         for j in range(length):
    
12.             if i<=j :
    
13.                 mat1[i,j] =min(o_list[i],o_list[j]) * abs(i-j)
    
14. 
    
15.     #print(mat1)
    
16.     #print("Max.Area = ", mat1.max())
    
17. 
    
18.     return (mat1.max())
    
19. 
    
20. r = max_area([1,8,6,2,5,4,8,3,7])
    

复制代码

在题目截止的最后一秒，如果是奇数我就回答，偶数我就不回答，我岂不是可以控制竞猜结果。

shigure_takimi

1. def max_area(list_of_number):
   
2.     length = len(list_of_number)
   
3.     s_list = []
   
4.     for index1 in range(length):
   
5.         for index2 in range(index1+1, length):
   
6.             a = index2 - index1
   
7.             b = min(list_of_number[index1], list_of_number[index2])
   
8.             s = a * b
   
9.             s_list.append(s)
   
10.     result_of_max_area = max(s_list)
    
11.     return result_of_max_area
    
12. 
    
13. 
    
14. list_of_number = [1,8,6,2,5,4,8,3,7]
    
15. 
    
16. print(max_area(list_of_number))

复制代码

shigure_takimi

1. def max_area(list_of_number):
   
2.     length = len(list_of_number)
   
3.     result_of_max_area = 0
   
4.     for index1 in range(length):
   
5.         for index2 in range(index1+1, length):
   
6.             a = index2 - index1
   
7.             b = min(list_of_number[index1], list_of_number[index2])
   
8.             area = a * b
   
9.             if area > result_of_max_area:
   
10.                 result_of_max_area = area
    
11.     return result_of_max_area
    
12. 
    
13. 
    
14. list_of_number = [1,8,6,2,5,4,8,3,7]
    
15. 
    
16. print(max_area(list_of_number))
    

复制代码

蓝色王魂

改进了一下效率应该会快很多

1. def max_area(list_of_number):
   
2.     length = len(list_of_number)
   
3.     result_of_max_area = (length-1)*(min(list_of_number[0],list_of_number[-1]))
   
4.     for i in range(length):
   
5.         for j in range(i+result_of_max_area//list_of_number[i],length):
   
6.             area = (j - i)*(min(list_of_number[i], list_of_number[j]))
   
7.             if area > result_of_max_area:
   
8.                 result_of_max_area = area
   
9.     return result_of_max_area

复制代码

蓝色王魂

蓝色王魂 发表于 2017-11-27 11:55
改进了一下效率应该会快很多

把多余的try-except去掉了，我以为range函数当起始值大于终止值时会报错呢。

sjf418926

见面会

shuo

1. def max_area(list_of_number):
   
2.     max_arrea = 0
   
3.     for i in (0,len(list_of_number)):
   
4.          for j in (0,len(list_of_number)):
   
5.               if i == j:
   
6.                   continue
   
7.               height = list_of_number[i] if list_of_number[i] > list_of_number[j] else list_of_number[j]
   
8.               weight = abs(i - j)
   
9.               area = height * weight
   
10.              max_area = area if area > max_area else max_area
    
11.     return max_area

复制代码

水平有限，实在想不出怎么优化，坐等题主答案呢。

shuo

shuo 发表于 2017-11-27 16:06
水平有限，实在想不出怎么优化，坐等题主答案呢。

是的， 已改正。 感谢指出。

shuo

shuo 发表于 2017-11-27 16:41
是的， 已改正。 感谢指出。

非常感谢 楼主的耐心指出。 改正后代码如下。

1. def max_area(list):
   
2.    max_area = 0
   
3.    for i in range(0,len(list)):
   
4.        for j in range(0,len(list)):
   
5.             if i == j :
   
6.                  continue
   
7.             height = list[i] if list[i] < list[j] else list[j]
   
8.             weight = abs(i - j)
   
9.             area = height * weight
   
10.             max_area = area if area > max_area else max_area
    
11.   return max_area

复制代码

sky

1. from itertools import combinations
   
2. 
   
3. def area(points):
   
4.     (ax, ay), (bx, by) = points
   
5.     return abs(bx - ax) * min(ay, by)
   
6. 
   
7. def max_area(list_of_number):
   
8.     coordinates = ((x, y) for x, y in enumerate(list_of_number))
   
9.     buckets = combinations(coordinates, 2)
   
10.     result_of_max_area = max(area(i) for i in buckets)
    
11.     return result_of_max_area

复制代码