arrays - 平衡数组子区间中元素数量的算法？

Question

假设您有一个包含 4 种不同类型元素的数组。

1 1 2 3 1 2 2 3 3 4 4 1.

我想找到导致每个元素数量相等且元素总数最大的最长子区间。

在这种情况下，它将是

1 1 2 3 1 2 2 3 3

因为这会导致 3 个二分球、3 个三分球和 3 个一分。

我相信这是某种修改后的动态规划，或者需要前缀和的东西，但我不太确定。有人可以告诉我如何开始吗？

Answer 1

#!/usr/bin/env python

#The demo data
SET = [1,1,2,3,1,2,2,3,3,4,4,1]

#Function to map the counts of the values in the set
def map(x):
        ret = {}
        for v in x:
                if v not in ret.keys():
                        ret.update({v:0})
                ret[v] += 1
        return ret

#Function to check if all counts in the map are the same
def checkMap(x):
        val = None
        for k,v in x.items():
                if val != None and v != val:
                        return False
                else:
                        val=v
        return True

#Determine the initial counts
counts = map(SET)

#Now step back from end index to start
for ix in range(len(SET) - 1, 0, -1):
        val = SET[ix]
        counts[val] += -1
        if counts[val] == 0:
                del counts[val]
        if checkMap(counts):
                print "Condition Reached, Largest Subset is:",SET[0:ix]
                break