algorithm - 最大子集总和

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(2^n) 时间复杂度)。

这是一个简单而高效的(O(N) 时间，O(1) 额外空间)方法:

1. 如果列表中至少有一个非负数，则返回所有正数的总和。

2. 否则返回列表中最大的元素。

这是一些代码:

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)