数组选元素求最大和：如何避免递归深度超限并优化解法？

首先明确核心规则：
给定长度为n的数组，需进行m = (n + 1) // 2次操作（每次操作后数组首尾各丢弃一个元素，直到为空）。第k次操作（0≤k<m）时，必须从原数组的区间[k, n-1-k]中选择一个未被选过的元素，将其值加入总和，目标是最大化总和。

思路 #

由于区间是嵌套的（第0层区间包含第1层，第1层包含第2层，依此类推），内层区间的可选元素更少。优先给最内层（最大k）的区间分配最大的可用元素，避免外层占用内层的稀缺可选资源，确保每一步选择都能最大化后续收益。

步骤 #

1. 将所有元素按值从大到小排序，保留原索引。
2. 维护两个标记数组：used_idx标记索引是否被选，filled_layer标记第k层是否已选元素。
3. 遍历排序后的元素，为每个元素分配其能归属的最大k层（满足元素在该层区间内、层未被填充、索引未被选），累加元素值到总和。

代码实现 #

def max_sum(arr):
    n = len(arr)
    m = (n + 1) // 2
    # 按元素值降序排序，保存(值, 原索引)
    sorted_elements = sorted([(val, idx) for idx, val in enumerate(arr)], reverse=True)
    used_idx = [False] * n
    filled_layer = [False] * m
    total = 0
    
    for val, idx in sorted_elements:
        # 当前元素能归属的最大k值
        max_k = min(idx, (n-1) - idx)
        # 从最大的k开始找未填充的层
        for k in range(max_k, -1, -1):
            if k >= m:
                continue
            if not filled_layer[k] and not used_idx[idx]:
                total += val
                used_idx[idx] = True
                filled_layer[k] = True
                break
    return total

# 测试用例
print(max_sum([4,4,8,5,3,2]))  # 输出17
print(max_sum([1,5,5,2]))       # 输出10

思路 #

用二进制掩码mask记录已选的索引，dp[mask]表示选了mask对应索引后的最大总和。遍历所有可能的掩码状态，逐步填充每个操作层的选择，最终取选满m个元素的掩码中的最大值。

代码实现 #

def max_sum_dp(arr):
    n = len(arr)
    m = (n + 1) // 2
    size = 1 << n
    dp = [-float('inf')] * size
    dp[0] = 0
    
    for mask in range(size):
        k = bin(mask).count('1')
        if k >= m:
            continue
        # 当前操作层对应的区间
        l, r = k, n-1 - k
        for i in range(l, r+1):
            if not (mask & (1 << i)):
                new_mask = mask | (1 << i)
                dp[new_mask] = max(dp[new_mask], dp[mask] + arr[i])
    # 找选满m个元素的最大总和
    max_total = 0
    for mask in range(size):
        if bin(mask).count('1') == m:
            max_total = max(max_total, dp[mask])
    return max_total

# 测试用例
print(max_sum_dp([4,4,8,5,3,2]))  # 输出17
print(max_sum_dp([1,5,5,2]))       # 输出10

如果坚持使用递归DP，可通过以下两种方式避免栈溢出：

1. 增加递归深度限制：在Python中执行import sys; sys.setrecursionlimit(100000)，但仅适合中等规模的n，极端大n仍会出问题。
2. 转为迭代实现：用手动栈模拟递归过程，维护递归所需的状态参数（如当前区间、已选元素标记），替代Python默认的递归栈。

内容的提问来源于stack exchange，提问作者isuf