Dylan.K's Blog

阿德的个人博客

0%

最大子数组问题

发表于 更新于 分类于

1 采用分治法

思想

将数组划分为左右两部分，查找左半部分与右半部分的最大子数组 与 当前问题类似，采用递归即可。

主要问题集中如何解决“最大子数组出现在跨域左右两部分”的时候，此时仅需从中间位置向两边查找最大和的边界位置即可。

时间复杂度: O(nlogn)

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def find_maximum_subarray(array, low=0, high=None):
    """
    最大子数组分治递归算法实现
    :param array: list
    :param low: int, 下边界
    :param high: int, 上边界
    :return: int sum, int sub_low, int sub_high
    """
    if high is None:
        high = len(array) - 1

    if low >= high:
        return array[low], low, low 

    mid = (low + high) // 2
    
    # 左半部查找
    left_max_sum, left_low, left_high = find_maximum_subarray(array, low, mid)

    # 右半部查找
    right_max_sum, right_low, right_high = find_maximum_subarray(array, mid+1,
                                                                 high)

    # 横跨左右查找
    # 由中间向左
    max_sum_l = cur_sum = array[mid]
    left = mid
    i = mid - 1
    while i >= left:
        cur_sum += array[i]
        if cur_sum > max_sum_l:
            max_sum_l = cur_sum 
            left = i
        i -= 1
    # 由中间向右
    max_sum_r = cur_sum = array[mid+1]
    right = mid+1
    j = mid+2
    while j <= high:
        cur_sum += array[j]
        if cur_sum > max_sum_r:
            max_sum_r = cur_sum 
            right = j
        j += 1
    cross_max_sum, cross_low, cross_high = max_sum_l+max_sum_r, left, right

    # 比较取最大
    if left_max_sum >= right_max_sum and left_max_sum >= cross_max_sum:
        return left_max_sum, left_low, left_high 
    elif right_max_sum >= left_max_sum and right_max_sum >= cross_max_sum:
        return right_max_sum, right_low, right_high 
    else:
        return cross_max_sum, cross_low, cross_high


if __name__ == "__main__":
    array = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
    s, l, h = find_maximum_subarray(array)
    print(f'max_sum={s}, low_pos={l}, high_pos={h}')

2 采用非递归、线性时间的算法

思想

出自《算法导论》4.1-5练习题：

使用如下思想为最大子数组问题设计一个非递归的、线性时间的算法。从数组的左边界开始，从左至右处理，记录到目前为止已经处理过的最大子数组。若已知A[1..j]的最大子数组，基于如下性质将解扩展为A[1..j+1]的最大子数组：A[1..j+1]的最大子数组要么是A[1..j]的最大子数组，要么是某个子数组A[i..j+1] (1≤i≤j+1)。在已知A[1..j]的最大子数组的情况下，可以在线性时间内找出形如A[i..j+1]的最大子数组。

划重点: A[1..j+1]的最大子数组要么是A[1..j]的最大子数组，要么是某个子数组A[i..j+1] (1≤i≤j+1)

在将数组由左向右处理时，A[1..j]的最大子数组是已求解，即已知的，需要求解的就是子数组A[i..j+1] (1≤i≤j+1)。此处对于数组A[i..j+1]要查找的最大解是包含边界A[j+1]的，否则就落入了对立条件A[1..j]数组中了。

对于寻找包含边界A[j+1]在内的最大解的数组A[i..j+1]而言，最大解要么仅仅就是元素A[j+1]，要么就是A[j+1]及其前面元素一起。而对于A[j+1]及其前面元素一起的情况，其中隐含的条件是一定包含了以A[j] （A[j+1]的前一个元素）为边界的最大解，换言之，此种情况就是A[j+1]+(A[i..j]的最大解）。

算法由左向右处理数组时，需要记录的值有：

  • A[1..j]的最大子数组及其和 (注：此处的最大子数组不一定包含边界A[j],可能位于1与j的开区间内）
  • A[i..j] (1≤i≤j)的最大子数组及其和 (注：此处的最大子数组是一定包含边界A[j]在内的，即以A[j]为起始向左前寻找最大的解，不同于上一个值）

比较过程：

  • 比较A[i..j] (即包含边界A[j]) + A[j+1] 与A[j+1]的大小，大者为A[i..j+1]的最大解
  • 比较A[1..j]与A[i..j+1]的最大解，大者为A[1..j+1]的最大解

时间复杂度：O(n)

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def find_maximum_subarray_linear(array):
    """
    最大子数组非递归线性时间算法实现
    :param array: list
    :return: int sum, int sub_low, int sub_high
    """
    j = 0
    end = len(array) - 1

    # Initialize the values of A[1..j]
    max_sum = array[0]
    sub_low = 0
    sub_high = 0

    # Initialize the values of A[i..j]
    boundary_max_sum = array[0]
    boundary_sub_low = 0
    boundary_sub_high = j
    
    # Not optimized code such as j+1 etc. on account of implementing the
    # algorithm according to the above description.
    while (j+1) <= end:
        # Find A[i..j+1]        
        if (boundary_max_sum + array[j+1]) > array[j+1]:
            boundary_max_sum += array[j+1]
            boundary_sub_high = j+1
        else:
            boundary_max_sum = array[j+1]
            boundary_sub_low = boundary_sub_high = j+1

        # Find A[1..j+1]
        if boundary_max_sum > max_sum:
            max_sum = boundary_max_sum
            sub_low = boundary_sub_low
            sub_high = boundary_sub_high

        j += 1

    return max_sum, sub_low, sub_high
        

if __name__ == "__main__":
    array = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
    s, l, h = find_maximum_subarray_linear(array)
    print(f'max_sum={s}, low_pos={l}, high_pos={h}')