修改bug

p某看见Q头上的bug太多了

题目

分析

可以看做，n个数的数组，中每次消除连续个相同的数，使每次消除个数的平方和最大。首先找到个数最多的数字，然后按照数字最多的位置将原数组划分成多个子数组，可以递归求每个子数组的最大bug数。数组中可能会出现个数相同的多个数字，需要对每个数字分别计算，找到不同划分的最大值。

python源码

#递归最大bug数
def maxbug(balls):
    if len(balls)==1:
        return  1
    max_index=select(balls);
    max_sum=0
    for mi in max_index:
        sum= mi[1]*mi[1]
        index=0
        for i,m in enumerate(balls):
            if m==int(mi[0]):
                if i-index>=1:
                    #print('index', index, i - 1,mi,balls[index:i])
                    sum+=maxbug(balls[index:i])
                index=i+1
            if i==len(balls)-1:
                if i-index>=0:
                   # print('index', index, i ,mi,balls[index:i])
                    sum+=maxbug(balls[index:i+1])
        if sum>max_sum:
            max_sum=sum
        #print('sum',sum)
    return max_sum
#每次选出数组中个数最大的一个或者多个数
def select(balls):
    temp={}
    for ball in balls:
        if str(ball) in temp.keys():
            temp[str(ball)]+=1
        else:
            temp[str(ball)]=1
    temp = sorted(temp.items(), key=lambda x: x[1], reverse=True)
    #print(temp)
    result=[]
    max=temp[0][1]
    #print('max:',max)
    for i in temp:
        if i[1]==max:
            result.append(i)
    return result

balls=[2,1,6,10,8,8,6,3,2,1]
balls=[8,6,2,6,6,3,2,3,2,2]
print(maxbug(balls))