子串和子序列（python）

• 子串：串中任意个连续的字符组成的子序列称为该串的子串；
• 子序列：序列的一部分项按原有次序排列而得的序列；

# -*- 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))