CODEWITHSUNDEEP
algorithmsubset-sum
Keselme
Keselme

Reputation: 4249

Maximum Sub-Set Sum

I'm trying to solve a slightly different variation of the Maximum Sub-Set Sum problem. Instead of consecutive elements, I want to find the elements that gives you the largest sum in the array. For example, given the following array:

{1,-3,-5,3,2,-7,1} the output should be 7 ( the sub-array with largest sum is {1,3,2,1} ).

Here the code I use to calculate the max sum:

    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));
    }

It works when I use positive and negative numbers together in the same array. However, the problem starts when I use only negative numbers - the output always is 0. I guess it happens because I send 0 as the sum at the very first time when I call the function. Can someone tell me how should I change my function so it will work with only negative numbers as well.

Upvotes: 0

Views: 145

Answers (2)

kraskevich
kraskevich

Reputation: 18556

Your solution is unnecessarily complicated and inefficient (it has an O(2^n) time complexity).

Here's a simple and efficient (O(N) time, O(1) extra space) way to do it:

  1. If there's at least one non-negative number in the list, return the sum of all positive numbers.

  2. Return the largest element in the list otherwise.

Here's some code:

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)

Upvotes: 3

97amarnathk
97amarnathk

Reputation: 1035

The special case would be when all elements are negative. In this case find the least negative number. That would be your answer. This can be done in O(N) time complexity.

PSEUDO CODE

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
    ...

Upvotes: 0

Related Questions