最大子串

发表于 | 分类于

问题描述

给定n个整数组成的序列，求该序列所有子序列中和最大的一个。例如序列为 0,-1,-2,3,2 时，最大子序列为 3,2，最大值为5。

问题分析

我们先进行穷举，计算所有子序列，然后找出最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 1.穷举
def sol1(nums):
    N = len(nums)
    s = 0
    max_sub = s
    left = right = 0
    for i in range(N):
        s = 0
        for j in range(i,N):
            s = sum(nums[i:j+1])
            if s > max_sub:
                max_sub = s
                left = i
                right = j
    return max_sub,left,right

我们用s(i,j)来表示起点为i，终点为j的子序列，遍历所有子序列时,先遍历起点i，时间复杂度O(n),再遍历终点j，复杂度也为O(n),对于每个子序列，i和j确定后，计算该序列的和也为O(n)，故该方法的总时间复杂度为O(n^3)。
我们用一个矩阵来表示所有的子序列，如下所示：

0 1 2 … n-1
s(0,0) s(0,1) s(0,2) … s(0,n-1)
0 s(1,1) s(1,2) … s(1,n-1)
0 0 s(2,2) … s(2,n-1)
… … .. … …
0 0 0 … s(n-1,n-1)

我们的目标就是计算出这个矩阵，然后找出最大值，穷举法的计算过程是从左向右，从上到下。观察到，每个子序列都可以由之前已经计算出的序列得到。例如 s(0,1)=s(0,0) + nums[1]，我们可以得到下面这个公式：

穷举时，我们每一项都要重新计算，现在我们每一项只需要常数时间就可以计算出，此时时间复杂度为O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 2.动态规划
def sol2(nums):
    N = len(nums)
    matrics = np.zeros((N,N),dtype=int)
    for i in range(N):
        for j in range(i,N):
            if i == j:
                matrics[i,j] = nums[i]
            else:
                matrics[i,j] = matrics[i,j-1] + nums[j]
    position = np.argmax(matrics)
    left = position // N
    right = position % N
    return matrics[left,right],left,right

我们可以比较一下两个算法的时间：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 时间比较
N = 1000
nums = np.random.randint(low=-N/2,high=N/2,size=N)
sol1_start = time.clock()
sol1(nums)
sol1_end = time.clock()
print("穷举法cpu时间:",sol1_end-sol1_start)
sol2_start = time.clock()
sol2(nums)
sol2_end = time.clock()
print("动态规划cpu时间:",sol2_end-sol2_start)

1
2
穷举法cpu时间: 31.870616599999998
动态规划cpu时间: 0.7049935000000005

可以看到当序列长度为1000时，相差已经很大了。