子串：串中任意个连续的字符组成的子序列称为该串的子串；子序列：序列的一部分项按原有次序排列而得的序列；
# -*- coding=utf-8 -*-
##### 1: 连续子串最大和 #####
def MaxSum(arr):
res, s = arr[0], arr[0]
for x in arr[1:]:
s = max(x, s+x)
res = max(res, s)
return res
##### 2: 连续子串最大乘积 #####
def MaxMulti(arr):
maxA, minA = [arr[0]], [arr[0]]
res = arr[0]
for i in range(1, len(arr)):
maxA.append(max(arr[i], maxA[i-1]*arr[i], minA[i-1]*arr[i]))
minA.append(min(arr[i], maxA[i-1]*arr[i], minA[i-1]*arr[i]))
res = max(res, maxA[-1])
return res
#### 3：最长递增子序列 ####
def LIS(arr):
dp = [1] * len(arr)
for i in range(len(arr)):
temp = 1
for j in range(i-1, -1, -1):
if arr[i] > arr[j]:
temp = max(temp, dp[j]+1)
dp[i] = temp
return max(dp)
#### 4：最长公共子串 ####
def LongSubStr(s1,s2):
dp = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]
res = 0
for i in range(1, len(s1)+1):
for j in range(1, len(s2)+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
res = max(res, max(dp[i]))
return res
#### 5：最长公共子序列 ####
def LongSubSeq(s1,s2):
dp = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]
res = 0
for i in range(1, len(s1)+1):
for j in range(1, len(s2)+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
res = max(res, max(dp[i]))
return res
#### 6：最长回文子串 ####
def LongPalindrome(s):
dp = [[False]*len(s) for _ in range(len(s))]
res = ''
for x in range(len(s)):
for i in range(len(s)-x):
j = i + x
if x == 0:
dp[i][j] = True
elif x == 1:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])
if dp[i][j] and j-i+1 > len(res):
res = s[i:j+1]
return res
#### 7：最长回文子序列 ####
def LongPalindromeSubseq(s):
dp = [[0] * len(s) for _ in range(len(s))]
for i in range(len(s)-1, -1, -1):
dp[i][i] = 1
for j in range(i+1, len(s)):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][-1]
num = [1,3,4,0,6,5,-1,2]
s1 = 'ASDSVAFA'
s2 = 'ABDSVSDF'
print(MaxSum(num), MaxMulti(num), LIS(num))
print(LongSubStr(s1, s2), LongSubSeq(s1,s2))
print(LongPalindrome(s1), LongPalindromeSubseq(s1))
