def contains(A, v):
for i in range(len(A)):
if A[i] == v: return True
return False
Decrease & Conquer O(n)
def contains(A, v, i=0):
if i >= len(A) or i < 0:
return False
if A[i] == v:
return True
return contains(A, v, i+1)
Divide & Conquer O(n)
def contains(A, v, i=0, j=None):
if j is None:
j = len(A)
if j - i == 0:
return False
c = (i+j) // 2
if A[c] == v:
return True
return contains(A, v, i, c) or contains(A, v, c+1, j)
Greedy, if sorted A O(logn)
def contains(A, v, i=0, j=None):
if j is None:
j = len(A)
if j - i == 0:
return False
c = (i+j) // 2
if A[c] == v:
return True
elif A[c] > v:
return contains(A, v, i, c)
else:
return contains(A, v, c+1, j)
Max Subarray Sum
Problem: 给定一个长度为 n 的整数数组 A,找到和最大的子数组
Example:
Input: A=[−9,1,−5,4,3,−6,7,8,−2]
output: 16
Brute Force O(n3)
遍历所有可能的子数组:
长度 = 1 的子数组 (1n) ,长度 > 1 的子数组 (2n) ,总数为 O(n2)
对长度为 k 的子数组求和,时间复杂度为 O(k)
总体时间复杂度为 O(n3)
def MSS(A):
m = A[0]
for j in range(1, len(A)+1):
for i in range(0, j):
m = max(m, SS(A, i, j))
return m
def SS(A, i, j):
s = 0
for k in range(i, j):
s += A[k]
return s
Divide & Conquer O(nlogn)
最大子数组有三种可能:整体位于左半边、整体位于右半边,横跨左右半边
计算图为树形
T(n)=2T(n/2)+O(n)=>T(n)=O(nlogn)
def MSS(A, i=0, j=None):
if j is None:
j = len(A)
if j - i == 1:
return A[i]
c = (i+j)//2
return max(MSS(A, i, c),
MSS(A, c, j),
MSS_EA(A, i, c) + MSS_SA(A, c, j))
def MSS_SA(A, i, j):
s = m = A[i]
for k in range(1, j-i):
s += A[i+k]
m = max(s, m)
return m
def MSS_EA(A, i, j):
s = m = A[j-1]
for k in range(1, j-i):
s += A[j-1-k]
m = max(s, m)
return m
Dynamic Programming
如果MSS_EA(A,0,k) 表示 A 中以第 k 个元素结尾的子数组,以下简称 (A,0,k) ,问题就按如下方式解决:
def MSS(A):
m = A[0]
for k in range(len(A)):
s = MSS_EA(A, 0, k+1)
m = max(m, s)
return m