字符串-动态规划

一、题目列表

题目1、字符串最长无重复子串

题目2、连续子数组和最大

题目1、字符串最长无重复子串

1.思路

用两个指针
(1)先定义三个变量，start = 0 左指针，max_len = 1 长度，dic = {} 字典，存储中间key是字符，value是位置
(2)用一个循环 for i in range(len(arr)),i代表右指针
≈

2.代码

class Solution:
    def maxLength(self , arr ):
        # write code here
        if len(arr) == 0:
            return 0
        start = 0
        max_len = 1
        dic = {}
        for i in range(len(arr)):                       ###  如果不加限制条件 
            if arr[i] in dic and dic[arr[i]] >= start:  ### abc cb第二个c进来后跟新左指针,第二个b
                start = dic[arr[i]] + 1                 ### 进来后，会把左指针向左更新。
            dic[arr[i]] = i
            max_len = max(max_len, i-start+1)
        return max_len

题目2、连续子数组和最大

1.思路

三行代码：利用动态规划的思想
(1)要求长度为n的子数组和最大，可以先求长度为2，3，4
(2)让数组每个值更新为当前长度最大的值就行

2.代码

(1)方法一:暴力求解

array = [1,-1,2,4,-3]
re = []
for i in range(len(array)):
    for j in range(len(array)):
        re.append(sum(array[j:j+i+1]))
print max(re)

(2)方法二:递归，动态规划

array = [1,-1,2,4,-3]
for i in range(1,len(array)):
    array[i]=max(array[i-1]+array[i],array[i])
print max(array)