Python-算法思维-4.2递归与分治1：数字三角形、最大子序列积

Python-算法思维-4.2递归与分治1：数字三角形、最大子序列积 第1关：数字三角形中路径最小积

本关任务：在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字的乘积最小，路径上的每一步都只能往左下或右下走，只需求出最小的乘积，不需要给出具体路径。 2 3 8 1 2 2 4 7 1 4 8 5 2 6 5输入的第一行为数字三角形的层数，后面为数字三角形。

n = eval(input())
A=[]
for i in range(n):
    X = A.append(list(map(int, input().split())))

def MinRouteProd(i,j):
    ########## begin ##########
    # 请在此填写代码，返回以i,j为顶点的最小路径积
    if i==n-1:
        return A[i][j]
    return A[i][j]*min(MinRouteProd(i+1,j),MinRouteProd(i+1,j+1))
    ########## end ##########
    return result
print(MinRouteProd(0,0))

第2关：最大子序列积

本关任务：对于一个浮点数序列A，只包含正数，找到一个子序列，使得该子序列中元素的乘积是最大的；输出这个最大的乘积。

输入的第一行是序列的元素总数，第二行是以空格隔开的浮点数序列； 输出的数据精确到小数点后2位，不足的位补0

根据提示，在右侧编辑器补充代码，计算并输出最大子序列的乘积。

n = eval(input())
A= list(map(float, input().split()))

#求A[low..high]中跨越mid的最大子序列积
def FindMaxCrossing(A,low,mid,high):
    ########## begin ##########
    leftSum=-1e50
    sum0=1
    for i in range(mid,low-1,-1):
        sum0*=A[i]
        leftSum=max(leftSum,sum0)
    rightSum=-1e50
    sum0=1
    for i in range(mid+1,high+1):
        sum0*=A[i]
        rightSum=max(rightSum,sum0)
    return leftSum*rightSum    
    ########## end ##########
    
    
#求A[low..high]中的最大子序列积
def FidMax(A,low,high):
    ########## begin ##########
    # 请在此填写代码，返回区间[low,high]的最大子序列积
    if low==high: return A[low]
    mid=(low+high)//2
    leftSum=FidMax(A,low,mid)
    rightSum=FidMax(A,mid+1,high)
    crossSum=FindMaxCrossing(A,low,mid,high)
    return max(leftSum,rightSum,crossSum)    
    ########## end ##########    
    
result = FidMax(A,0,len(A)-1)
print('%.2f' % result)

求求三连啦。。。