Given an array of integers, describe an algorithm to find the largest subset sum. Discuss the complexity of your solution. Implement the solution in code.
Sigiloso
I am assuming the largest contiguous sublist sum and also that only the sum value matters (since in the problem description doesn't say anything about returning the elements themselves). Let's assume the array has size n (ranging from 0...n-1). For every element i, just calculate the largest sum that ranges from 0 to i and includes i. This sum will either be element[i] or element[i]+previousSum. Do this for the whole array and store, maximum value and return it. int largestSublisttSum(int* elements, int size) { int i = 0; int result, previousSum; previousSum = result = aux[i++] = elements[0]; for(;i largestSublistCandidate) { currentSum = elements[i]; } else { currentSum = largestSublistCandidate; } if(currentSum > result) { result = currentSum; } previousSum = currentSum; } return result; }