鱼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块木板见的水面积是这样的。


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

def max_area(list_of_number):
    '''your code here'''
    return result_of_max_area

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

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

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

截止日期： 11月30日0时

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

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

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

冬雪雪冬

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


还是这样

BngThea

def max_area(lst):
    length = len(lst)
    area = []
    for i in range(length - 1):
        temp = []
        for j in range(i + 1,length):
            temp.append((j - i) * (lst[i] if lst[i] < lst[j] else lst[j]))            
        area.append(max(temp))
    return max(area)


lst = [1,8,6,2,5,4,8,3,7]
print(max_area(lst))

yjsx86

L = [1, 8, 6, 2, 5, 4, 8, 3, 7]

def max_area(_list):
    rs = []
    for i in range(len(_list)):
        for j in range(i, len(_list)):
            rs.append((_list[i] if _list[i] < _list[j] else _list[j]) * abs(i - j))
    return max(rs)

print(max_area(L))

aegis1417

試試水溫

def max_area(list_of_num):
        from itertools import combinations
        b=[i for i in range(len(list_of_num))]
        a=list(combinations(b, 2))
        d=[]
        for i in a:
                if list_of_num[i[0]]>list_of_num[i[1]]:
                        d.append(list_of_num[i[1]]*(i[1]-i[0]))
                else:
                        d.append(list_of_num[i[0]]*(i[1]-i[0]))
        return print(max(d))

max_area([1,8,6,2,5,4,8,3,7])

蓝色王魂

def max_area(list_of_number):
    length = len(list_of_number)
    result_of_max_area = 0
    for i in range(length):
        for j in range(i+1,length):
            area = (j - i)*(min(list_of_number[i], list_of_number[j]))
            if area > result_of_max_area:
                result_of_max_area = area
    return result_of_max_area

SixPy

import numpy as np
def max_area(ls):
    a = np.array(ls)
    x,y = np.triu_indices(len(ls),1)
    return (np.where(a[x]<a[y],a[x],a[y])*(y-x)).max()

ls = [1,8,6,2,5,4,8,3,7]
print(max_area(ls))
#49

SixPy

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

一片模糊望尘世

def max_area(nums):
    l = 0
    r = len(nums) - 1
    area = 0
    for width in range(len(nums) - 1, 1, -1):
        height = min(nums[l], nums[r])
        area = max(area, height * width)
        if nums[l] > nums[r]:
            r -= 1
        else:
            l += 1

    return area

梦想绘制者

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

Elastcio

def max_area(o_list):

    import numpy as np

    #o_list = [1,8,6,2,5,4,8,3,7]

    length = len(o_list)
    mat1 = np.mat(np.zeros((length,length)))

    for i in range(length):
        for j in range(length):
            if i<=j :
                mat1[i,j] =min(o_list[i],o_list[j]) * abs(i-j)

    #print(mat1)
    #print("Max.Area = ", mat1.max())

    return (mat1.max())

r = max_area([1,8,6,2,5,4,8,3,7])

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

shigure_takimi

def max_area(list_of_number):
    length = len(list_of_number)
    s_list = []
    for index1 in range(length):
        for index2 in range(index1+1, length):
            a = index2 - index1
            b = min(list_of_number[index1], list_of_number[index2])
            s = a * b
            s_list.append(s)
    result_of_max_area = max(s_list)
    return result_of_max_area


list_of_number = [1,8,6,2,5,4,8,3,7]

print(max_area(list_of_number))

shigure_takimi

def max_area(list_of_number):
    length = len(list_of_number)
    result_of_max_area = 0
    for index1 in range(length):
        for index2 in range(index1+1, length):
            a = index2 - index1
            b = min(list_of_number[index1], list_of_number[index2])
            area = a * b
            if area > result_of_max_area:
                result_of_max_area = area
    return result_of_max_area


list_of_number = [1,8,6,2,5,4,8,3,7]

print(max_area(list_of_number))

蓝色王魂

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

def max_area(list_of_number):
    length = len(list_of_number)
    result_of_max_area = (length-1)*(min(list_of_number[0],list_of_number[-1]))
    for i in range(length):
        for j in range(i+result_of_max_area//list_of_number[i],length):
            area = (j - i)*(min(list_of_number[i], list_of_number[j]))
            if area > result_of_max_area:
                result_of_max_area = area
    return result_of_max_area

蓝色王魂

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

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

sjf418926

见面会

shuo

def max_area(list_of_number):
    max_arrea = 0
    for i in (0,len(list_of_number)):
         for j in (0,len(list_of_number)):
              if i == j:
                  continue
              height = list_of_number[i] if list_of_number[i] > list_of_number[j] else list_of_number[j]
              weight = abs(i - j)
              area = height * weight
             max_area = area if area > max_area else max_area
    return max_area

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

shuo

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

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

shuo

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

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

def max_area(list):
   max_area = 0
   for i in range(0,len(list)):
       for j in range(0,len(list)):
            if i == j :
                 continue
            height = list[i] if list[i] < list[j] else list[j]
            weight = abs(i - j)
            area = height * weight
            max_area = area if area > max_area else max_area
  return max_area

sky

from itertools import combinations

def area(points):
    (ax, ay), (bx, by) = points
    return abs(bx - ax) * min(ay, by)

def max_area(list_of_number):
    coordinates = ((x, y) for x, y in enumerate(list_of_number))
    buckets = combinations(coordinates, 2)
    result_of_max_area = max(area(i) for i in buckets)
    return result_of_max_area