当前位置：首页 > article >正文

最大子数组问题非蛮力算法

article 2024/12/29 17:44:28

文章目录

原题链接
动态规划（Dynamic Programming） - Kadane算法
前缀和
- 用于解决变种题目
分治法（Divide and Conquer）
线段树（Segment Tree）

原题链接

53. 最大子数组和

动态规划（Dynamic Programming） - Kadane算法

时间复杂度： $O (n)$
思路：遍历数组，同时维护两个变量，一个是当前的最大子数组和，另一个是当前的最大子数组结束位置的连续和。在每一步更新这两个变量。
代码

def solution(nums):
	res=nums[0]
	cur=res
	for i, num in enumerate(nums[1:]):
		cur=max(num, cur+num)
		res=max(res, cur)
	return res

分析：给定数组的最大子数组满足最优子结构：将数组从右侧剪裁到以解结束的位置，这个解还是剪裁后的数组的最优解。这也说明最大子数组的最优解也是原问题某个子数组的最大后缀数组。枚举所有最大后缀数组即可。当我们遍历时，已知 $\text{nums}[i-1]$ 的最大后缀数组， $\text{nums}[i]$ 的最大后缀数组可以通过状态转移获得：
$\text{suffixs}[i]= \begin{cases} \text{nums}[i] &\text{if } \text{nums}[i] >\text{suffix}[i-1]+\text{nums}[i], \\ \text{suffix}[i-1]+\text{nums}[i] &\text{if }\text{suffix}[i-1]+\text{nums}[i]>\text{nums}[i]. \end{cases}$
即 $\text{suffixs}[i]=\max\{\text{nums}[i], \text{suffix}[i-1]+\text{nums}[i]\}$
最大子数组值为 $\max\{\text{suffixs}[i] | i\}$

前缀和

时间复杂度： $O (n)$
思路：先构建前缀和数组，然后遍历前缀和数组，任意子数组的和可通过前缀和数组的差分获得。同时维护两个变量，一个是当前的最大子数组和，一个是遍历过的最小前缀和。在每一步更新这两个变量。当前的最大子数组结束位置的连续和可以通过当前前缀和减最小前缀和获得。本质还是计算当前的最大子数组结束位置的连续和。
优点是更为灵活。缺点是时间复杂度虽然渐进 $O (n)$ 但是由于多次遍历相比Kadane算法实际时间复杂度系数更高。
代码

def solution(nums):
	prefixs=[nums[0]]
	for i, num in enumerate(nums[1:]):
		prefixs.append(prefixs[-1]+num)
	min_prefix=min(0, prefixs[0])
	res=prefixs[0]
	for i, prefix in enumerate(prefixs[1:]):
		res=max(res, prefix-min_prefix)
		min_prefix=min(min_prefix, prefix)
	return res

以下为常见错误代码：

def solution(nums):
	prefixs=[nums[0]]
	for i, num in enumerate(nums[1:]):
		prefixs.append(prefixs[-1]+num)
	min_prefix=prefixs[0]
	res=min_prefix
	for i, prefix in enumerate(prefixs[1:]):
		res=max(res, prefix-min_prefix)
		min_prefix=min(min_prefix, prefix)
	return res

最小前缀和的初始值应赋为0而不是前缀和的第一项，因为当前缀和中没有负数时，当前前缀和就是子数组的最大后缀数组和。

用于解决变种题目

周赛427-Q3: 长度可被K 整除的子数组的最大元素和

代码

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        prefix_sum = []
        prefix_sum.append(nums[0])
        for i, num in enumerate(nums[1:]):
            prefix_sum.append(prefix_sum[-1] + num)
        memo = [float('inf')]*k  # 取余桶-保存不同位置的最小值
        memo[k-1]=0
        res=float('-inf')
        for i, pre_sum in enumerate(prefix_sum, start=0):
            if i>=k-1:
                res = max(res, pre_sum-memo[i%k])
            if pre_sum < memo[i%k]:
                memo[i%k] = pre_sum
        return res©leetcode

分治法（Divide and Conquer）

时间复杂度： $\log n)$
思路：将数组分为两半，最大子数组可能出现在以下三种情况之一：
- 完全位于左半部分
- 完全位于右半部分
- 跨越中间点
对于前两种情况，可以递归解决。对于第三种情况，可以从中间点向左右扩展，找到最大的子数组。
代码

class Solution:
    
    def recursive(self, nums, lo, hi):
        if lo==hi-1:
            return nums[lo]
        mid = (lo+hi)//2
        l_max = -float("inf")
        r_max = -float("inf")
        l_sum = 0
        for i in range(mid-1, lo-1, -1):
            l_sum+=nums[i]
            l_max=max(l_max, l_sum)
        r_sum = 0
        for i in range(mid, hi):
            r_sum+=nums[i]
            r_max=max(r_max, r_sum) 
        l_r_max = max(self.recursive(nums, lo, mid), self.recursive(nums, mid, hi))
        return max(l_r_max, l_max+r_max)

    def maxSubArray(self, nums: List[int]) -> int:
        n=len(nums)
        self.dp=[[float("-inf")]*n for _ in range(n)]
        return self.recursive(nums, 0, len(nums))

分析：第三种情况从中间向两侧拓展并不需要检查所有起始与结束对（ $O(n^2)$ ），只需要分别检查两侧的后缀数组与前缀数组的最大值并相加（ $O (n)$ ）。
- 证明：假设横跨的最大子数组不是两个相加，则前后必有一部分大于最大的后缀数组或前缀数组，而此时找到了比最大的数组更大的数组，矛盾。因此横跨的最大子数组一定是后缀数组与前缀数组的最大值并相加。

线段树（Segment Tree）

时间复杂度： $O (n)$
思路：使用线段树来维护区间的和，可以快速查询和更新区间的最大子数组和。
代码

class Status:
    def __init__(self, l_max, r_max, m_max, i_sum):
        self.l_max=l_max
        self.r_max=r_max
        self.m_max=m_max
        self.i_sum=i_sum

class Solution:

    def pushUp(self, l_status, r_status):
        l_max = max(l_status.l_max, l_status.i_sum+r_status.l_max)
        r_max = max(r_status.r_max, r_status.i_sum+l_status.r_max)
        i_sum = l_status.i_sum+r_status.i_sum
        m_max = max([l_status.m_max, r_status.m_max, l_status.r_max+r_status.l_max])
        return Status(l_max, r_max, m_max, i_sum)
    
    def recursive(self, nums, lo, hi):
        if lo==hi-1:
            return Status(nums[lo], nums[lo], nums[lo], nums[lo])
        mid = (lo+hi)//2
        l_status = self.recursive(nums, lo, mid)
        r_status = self.recursive(nums, mid, hi)
        status = self.pushUp(l_status, r_status)
        return status

    def maxSubArray(self, nums: List[int]) -> int:
        return self.recursive(nums, 0, len(nums)).m_max