一、求旋轉數組最小值
假定一個排序數組以某個未知元素為支點做了旋轉，如：原數組0 1 2 4 5 6 7旋轉後得到4 5 6 7 0 1 2。請找出旋轉後數組的最小值。假定數組中沒有重複數字。
1、分析問題
旋轉之後的數組實際上可以劃分成兩個有序的子數組：前面子數組的大小，都大于後面子數組中的元素；4 5 6 7 0 1 2 注意到，實際上最小的元素就是兩個子數組的分界線。
2、解決思路
用兩個指針low、high分别指向數組的第一個元素和最後一個元素。如果是正常的排序數組(元素間不重複)，第一個元素肯定小于最後一個元素。
計算中間位置mid = (low+high)/2。
(1)、先考察A[mid]、A[low]關系
若：A[mid]>A[low]，則A[low,low+1….mid-1,mid]是遞增序列，最小元素位于子數組A[mid+1,mid+2,…high]中。是以，做指派low=mid+1。
若：A[mid]<A[low] ，則A[low,low+1….mid-1,mid]不是遞增序列，即：中間元素該子數組中，做指派high=mid。
(2)、再考察A[mid]、A[high]關系
對偶地，若考察A[mid]與A[high]的關系，能夠得到相似的結論。
二、求零子數組
求對于長度為N的數組A，求子數組的和接近0的子數組，要求時間複雜度O(NlogN)。
1、算法思路
申請同樣長度的空間sum[0…N-1]，sum[i]是A的前i項和。
Trick：定義sum[-1] = 0
顯然有：
算法：對sum[0…N-1]排序，然後計算sum相鄰元素的差，最小值記為min1。
min1：在A中任意取兩個集合，各自元素的和求差的最小值
因為sum[-1]=0，sum[0…N-1]的絕對值最小值記為min2。
min2：A的前k個元素的和的絕對值的最小值
min1和min2的更小者，即為所求。
2、要說明的兩個問題
sum本身的計算和相鄰元素差的計算，都是O(N)，sum的排序是O(NlogN)，是以，總時
間複雜度：O(NlogN)
強調：除了計算sum相鄰元素的差的最小值，别忘了sum自身的最小值。一個對應A[i…j]，一個對應A[0…j]
三、最長公共子串和最長公共子序列
1、最長公共子串(必須連續)—python實作
Longest Common Substring最長公共子串。
def LCS_find_Substring(s1, s2): #求兩個字元串最長公共子串
'''
用一個矩陣來記錄兩個字元串中所有位置的兩個字元之間的比對情況，
若是比對則為1,否則為0。
然後求出對角線最長的1的序列，其對應的位置就是最長比對子串的位置。
matrix_2D=[ [0 for i in range(len(s2)+1)]
for j in range(len(s1)+1)] #定義全0矩陣，為友善後續計算，比字元串長度多了一列
# print('生成(i+1)行、(j+1)列全0矩陣：',matrix_2D)
length_max=0 #最長比對的長度
p_end=0 #最長比對對應在s1中的最後一位
for i in range(len(s1)):
for j in range(len(s2)):
if s1[i]==s2[j]: #第一個if判斷，兩字元串内元素對應相等時，矩陣内，再次相等元素處的索引累計+1
matrix_2D[i+1][j+1]=matrix_2D[i][j]+1
if matrix_2D[i+1][j+1]>length_max: #第二個if判斷，将目前相等元素的個數，指派給length_max
length_max=matrix_2D[i+1][j+1]
p_end=i+1 #記錄s1中連續相等情況下，最後的索引位置
print(matrix_2D)
print(p_end,length_max)
return s1[p_end-length_max:p_end],length_max #傳回最長子串及其長度
s1=str(input())
s2=str(input())
res=LCS_find_Substring(s1, s2)
print(res)
2、最長公共子序列(可不連續)—python實作
Longest Common Subsequence，LCS 一個序列S任意删除若幹個字元得到新序列T，則T叫做S的子序列；兩個序列X和Y的公共子序列中，長度最長的那個，定義為X和Y的最長公共子序列。
比如：字元串"helloworld"和"loop"的最長公共子序列為loo；字元串acdfg與adfc的最長公共子序列為adf。
注意：差別最長公共子串，最長公共字串要求連續，而序列可以不連續。
def LCSubsequence(string1,string2):
len1 = len(string1)
len2 = len(string2)
res = [[0 for i in range(len1+1)] for j in range(len2+1)]
for i in range(1,len2+1):
for j in range(1,len1+1):
if string2[i-1] == string1[j-1]:
res[i][j] = res[i-1][j-1]+1
else:
res[i][j] = max(res[i-1][j],res[i][j-1])
return res,res[-1][-1]
print(LCS("helloworld","loop"))
2、LCS的意義
(1)、求兩個序列中最長的公共子序列算法，廣泛的應用在圖形相似處理、媒體流的相似比較、計算生物學方面。生物學家常常利用該算法進行基因序列比對，由此推測序列的結構、功能和演化過程。
(2)、LCS可以描述兩段文字之間的“相似度”，即它們的雷同程度，進而能夠用來辨識抄襲。另一方面，對一段文字進行修改之後，計算改動前後文字的最長公共子序列，将除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分準确。簡而言之，百度知道、百度百科都用得上。
3、求解
(1)、計算LCS長度
(2)、根據b提供的方向，構造最長公共子序列
(3)、最大公共子序列的多解性：求所有的LCS