We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Max Array Sum
  2. Discussions

Max Array Sum

  • vellavarun
     + 0 comments

    Solution: we start from the last element and we try to see if that element belongs to the max subset group. There can be 4 scenarios: * element belongs * adjancent elements belongs instead * element belongs with non-adjacent element * non-adjacebnt elemnt belongs instead * none belong, but that can be taken care of by making it recursively check what's best for the next step. Here's the code:

    # n <= 10^5
sys.setrecursionlimit(100000)

# Complete the maxSubsetSum function below.
def maxSubsetSum(arr):
    
    # for memoization
    cache = {}
    
    # subfunction for finding the right path
    def max_subarr(position):
        if position in cache:
            return cache[position]
        result = 0
        if position < 0:
            return result
        else:
            # choose the maximum between:
            # self, self + (non-adjacent next), adjacent next, non-adjacent next
            result = max(arr[position],
                        arr[position] + max_subarr(position-2),
                        max_subarr(position-1),
                        max_subarr(position-2))
        
        # print("position %s result %s" % (position, result))
        
        # cache for memoization
        cache[position] = result
        
        return result
        
    maxSubSum = max_subarr(len(arr)-1)
    return maxSubSum