平衡数组子间隔中元素数的算法？

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个1。

我相信这是某种修改的动态规划，或者需要前缀和的东西，但我不太确定。谁能给我个开场白吗？

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