首页 > 其他 > 详细

找出面积最大的矩形

时间:2019-01-12 11:56:46      阅读:55      评论:0      收藏:0      [点我收藏+]

标签:输入   .com   color   app   style   tps   pen   矩形   span   

描述

在一个平面图上,有多个宽度固定为1,高度不同的矩形并列排着,在这些矩形所组成的图形中,能够切割出的最大矩形的面积是多少? 数据范围:0 < 高度 < 100

举例:高度为2,3,2的三个矩形所组成的图形,能够切割出的最大的矩形面积为6。见下图。

技术分享图片

输入

 

一组正整数,分别用逗号隔开,表示每个矩形的高度

 

输出

 

一个整数,表示组合成的最大的矩形面积

 

输入样例

2,3,2
5,6,7,8,3

 复制样例

输出样例

6
20

def solution(line):
    nums=list(map(int,line.split(,)))

    def getMaxArr(arr,number):
        s=[]

        if len(arr)==0:
            return 0
        for i in range(len(arr)):
            if (i==0 or arr[i-1]<number) and arr[i]>=number:
                s.append([i,0])
            if i==len(arr)-1 or (arr[i-1]>=number and arr[i]<number):
                if len(s)>0:
                    if i==len(arr)-1 and arr[i]>=number:
                        s[-1][1]=i+1
                    else:
                        s[-1][1]=i
        are=0
        for i in s:
            are=max(are,max(len(arr[i[0]:i[1]])*number,getMaxArr(arr[i[0]:i[1]],number+1)))
        return are


    return getMaxArr(nums,1)

 

找出面积最大的矩形

标签:输入   .com   color   app   style   tps   pen   矩形   span   

原文:https://www.cnblogs.com/NewsunLs/p/10258994.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号