最大子集总和

Question

我正在尝试解决最大子集总和问题的一个稍微不同的变体。我想找到给你数组中最大和的元素，而不是连续的元素。例如，给定以下数组：

{1,-3,-5,3,2,-7,1} 输出应该是7（和最大的子数组是{1,3,2,1}）。

这里是我用来计算最大总和的代码：

    int max(int a, int b)
    {
        if (a >= b)

            return a;

        return b;
    }

    int func(List<Integer> l, int idx, int sum)
    {
        if (idx < 0)

            return sum;

        return max ( func(l,idx - 1, sum+l.get(idx)), func(l,idx-1,sum) );

    }

    public static void main(String[] args) {

        List<Integer> l = new LinkedList<Integer>();
        l.add(-2);
        l.add(-1);
        l.add(-3);
        l.add(-4);
        l.add(-1);
        l.add(-2);
        l.add(-1);
        l.add(-5);
        System.out.println(func(l,l.size()-1,0));
    }

当我在同一个数组中同时使用正数和负数时，它起作用了。但是，当我只使用负数时，问题就开始了——输出总是 0。我猜这是因为我在调用函数时第一次发送 0 作为总和。谁能告诉我应该如何更改我的函数，以便它也只适用于负数。

Answer 1

特殊情况是所有元素都为负数。在这种情况下，找到最小的负数。那就是你的答案。这可以在 O(N) 时间复杂度内完成。

伪代码

ALLNEG=true
LEAST_NEG= -INFINITY
for number in list:
    if number>=0
        ALLNEG=false
        break
    else if number>LEAST_NEG
        LEAST_NEG=number
if ALLNEG==true
    answer=LEAST_NEG
else
    ...

Answer 2

您的解决方案不必要地复杂且效率低下（它具有 O(2^n) 时间复杂度）。

这里有一个简单有效的（O(N) 时间，O(1) 额外 space）的方法：

如果列表中至少有一个非负数，return所有正数的总和
Return 否则为列表中最大的元素。

这是一些代码：

def get_max_non_empty_subset_sum(xs):
     max_elem = max(xs)
     if max_elem < 0:
          return max_elem
     return sum(x for x in xs if x > 0)

最大子集总和

Maximum Sub-Set Sum

algorithm

subset-sum