动态规划|python

先上代码：

class Solution:
    def maxLength(self, a):
        if len(a) == 1:
            return 1
        dp = [0]*(len(a)+1)
        dp[0] = 0
        cur_list = a[:1]
        for i in range(1, len(a)):
            progress = self.dp_len(cur_list, a[i])
            dp[i] = max(dp[i-1], progress[0])
            cur_list = progress[1]
        return max(dp)
    # update the situation
    def dp_len(self, temp, ele):
        while ele in temp:
            temp.pop(0)
        temp.append(ele)
        return len(temp), temp

从思路上可以理解为dp【i】与dp【i-1】取max，dp：指当前考虑第i个元素的最大长度与考虑第i-1个元素(不考虑第i个元素)的最长无重复数组
这里设置一个方法def dp_len(temp， ele)用于检测ele是否在temp里，并且更新temp返回更新后的temp和len(temp)用于后续的比较

def dp_len(temp, ele):
    while ele in temp:
        temp.pop(0)
    temp.append(ele)
    return len(temp), temp

Dynamic Programming中的状态更新算法为：

for i in range(1, len(a)):
    progress = dp_len(cur_list, a[i])
    dp[i] = max(dp[i-1], progress[0])
    cur_list = progress[1]

此处还需要在主code block中设置一个if判断，如果输入得len（a）== 1：
则直接返回
return 1