我正在尝试解决最大子集总和问题的一个稍微不同的变体。我想找到给你数组中最大和的元素,而不是连续的元素。例如,给定以下数组:
{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 作为总和。谁能告诉我应该如何更改我的函数,以便它也只适用于负数。
最佳答案
您的解决方案不必要地复杂且效率低下(它具有 O(2^n)
时间复杂度)。
这是一个简单而高效的(O(N)
时间,O(1)
额外空间)方法:
如果列表中至少有一个非负数,则返回所有正数的总和。
否则返回列表中最大的元素。
这是一些代码:
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)
关于algorithm - 最大子集总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44204888/