如何编写代码找出数组中获最大和的数值组合？含需求与示例

核心逻辑 #

问题要求找到数组中和最大的非空子序列（元素保持原数组顺序，可跳过任意元素），核心思路如下：

1. 优先筛选所有正数：正数的加入必然提升总和，只要数组存在正数，就应全部选中。
2. 全负数场景处理：若数组中没有正数，只能选择最大的那个负数（非空组合的前提下，负数中最大的元素和最小）。
3. 保持选中元素在原数组中的出现顺序。

注：你给出的第三个例子[3,-4,-1,-3]预期结果为2（组合[3,-1]）不符合常规逻辑，因为单独取3的和为3，比2更大，推测是例子存在笔误，或者需求有未明确的限制（比如必须选至少2个元素）。

代码实现（Python） #

通用实现（适配前两个例子，符合常规需求） #

def max_subsequence_sum(arr):
    if not arr:
        return (0, [])
    
    # 筛选数组中的所有正数
    positive_nums = [num for num in arr if num > 0]
    
    if positive_nums:
        total_sum = sum(positive_nums)
        return (total_sum, positive_nums)
    else:
        # 全为负数时，选最大的那个元素
        max_neg = max(arr)
        return (max_neg, [max_neg])

# 测试用例
print(max_subsequence_sum([1,2,3,4]))  # 输出：(10, [1, 2, 3, 4])
print(max_subsequence_sum([2,-3,7,-4,9]))  # 输出：(18, [2, 7, 9])
print(max_subsequence_sum([3,-4,-1,-3]))  # 输出：(3, [3])

适配强制选至少2个元素的场景 #

如果需求明确要求组合长度不能小于2，可使用以下实现（适合小容量数组，大数据组需优化）：

from itertools import combinations

def max_subsequence_sum_min_two(arr):
    if len(arr) < 2:
        return (sum(arr), arr) if arr else (0, [])
    
    max_sum = float('-inf')
    best_comb = []
    
    # 遍历所有长度≥2的子序列，保持原数组顺序
    for length in range(2, len(arr)+1):
        for comb in combinations(arr, length):
            current_sum = sum(comb)
            if current_sum > max_sum:
                max_sum = current_sum
                best_comb = list(comb)
    
    return (max_sum, best_comb)

print(max_subsequence_sum_min_two([3,-4,-1,-3]))  # 输出：(2, [3, -1])

补充说明 #

• 通用实现的时间复杂度为O(n)，效率极高，适合任意规模的数组。
• 强制选至少2个元素的实现时间复杂度为O(2^n)，仅适用于小容量数组，大数据组需采用动态规划进行优化。

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