CODEWITHSUNDEEP
pythonarraystime-complexitysubset
NhatHo
NhatHo

Reputation: 73

How to find the largest sum of the subset from a giving array. (Subset can't not have element greater than sum of any 2 elements)

I ran into an interested challenge in my coding interview. I need help finding another better way to solve the problem.

Problem: Giving an Arrays have N elements.

We need to return the largest sum of the subset which have this following condition.

Condition: Any elements in the subset can not be greater than the sum of any 2 elements in the subset.

The subset can be have 0 to N elements. If subset have 1 to 2 elements(don't need to follow Condition)

Example: N = [10,4,4,4,5]

The result will be 4+4+4+5 = 17. The output is 17

*Note: we only need to return the Sum (we don't need to return the subset)

2nd Example

N = [100,99,98,4,4,4,4,4,5]

The result will be 100+99+98. The output is 297

My solution:

I finding every possible subser, then I find the sum of any subset that satisfy the condition. Then I find the max sum of the subset

n = [100,4,4,4,5]
def findPossibleSum(n):
   n.sort()                                     #I sort the n so that it can be easier to check the condition later
   result_temp = 0
   result = max(n)                              #for situation that largest sum belong to 1 element subarray.
   for i in range(0,len(n)+1):
       for j in range(i+1,len(n)+1):            #find all subset
           if len(n[i:j]) == 2:                 #check subset that have 2 elements
               result_temp = sum(n[i:j])
           if len(n[i:j]) > 2:                  #subset that have more then 2 elements
               if n[j-1] < (n[i] + n[i+1]):     #Because I sort the n from beginning. Now that I can check the largest elements(which is the one on the right side) and the sum of smallest elements(2 on the left side).(to determine the condition)
                  result_temp = sum(n[i:j])
               else:
                  pass
           if result_temp > result:
               result = result_temp
     return(result)

My question: The time complexity of my solution is > O(N^3). Is there a way to do this problem in O(N) or O(N^2).

Upvotes: 1

Views: 1482

Answers (1)

Mo B.
Mo B.

Reputation: 5805

Here is an algorithm with complexity O(n log n), and it's not possible to do better than O(n log n) since you need to sort the array first. Once it's sorted, you can do the remaining work in O(n).

Observation 1

Consider a subset S that satisfies the condition with at least 3 elements. Then all subsets that contain numbers from the array A that are between min(S) and max(S) also satisfy the condition. Hence it is not necessary to consider all subsets of the array A. It is sufficient to sort A in descending order and only consider subarrays of the sorted A.

Observation 2

If the longest subarray satisfying the condition starting with index i has length k, then in order to find subarrays starting with an index j > i that satisfy the condition and have a greater sum than the first subarray, it is sufficient to only consider subarrays of length > k, since all other subarrays would have a smaller sum. That means that we only need to consider O(n) many candidate subarrays.

Observation 3

If the longest subarray satisfying the condition starting with index i has length k and its sum is x, then the sum of the subarray starting with index i+1 with length k is x - A[i] + A[i + k + 1], so the sum for the next candidate subarray can always be computed in constant time.

Algorithm (C#)

        int findMaxSum(int[] array)
        {
            if (array.Length == 0) return 0;

            Array.Sort(array);
            Array.Reverse(array);

            int k = 0;
            int maxSum = 0;
            int currentSum = array[0];

            for (int i = 0; i < array.Length; i++)
            {
                // find the longest subarray starting from i
                while (i + k + 1 < array.Length)
                {
                    if (k > 0 && array[i] > array[i + k] + array[i + k + 1])
                    {
                        // condition not satisfied, so we've found the longest subarray
                        k = k - 1;
                        break;
                    }
                    // grow the subarray and increase the current sum
                    k = k + 1;
                    currentSum = currentSum + array[i + k];
                }
                // check if the sum of the longest subarray starting from i is larger than the largest sum found so far
                maxSum = Math.Max(maxSum, currentSum);
                // subtract the first element to consider subarrays starting from i + 1
                currentSum = currentSum - array[i];
            }

            return maxSum;
        }

Complexity

Sorting the array is O(n log n). After that, we are growing a sliding subarray whose length is incremented until the condition is not met anymore, and which slides from left to right until the end of the array is hit. Hence despite the nested loop this takes O(n).

So overall complexity is O(n + n log n) = O(n log n).

Upvotes: 1

Related Questions