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

  • billptw
     + 9 comments

    Using tabulation (bottom up approach) in Python:

    def maxSubsetSum(arr):
    dp = {} # key : max index of subarray, value = sum
    dp[0], dp[1] = arr[0], max(arr[0], arr[1])
    for i, num in enumerate(arr[2:], start=2):
        dp[i] = max(dp[i-1], dp[i-2]+num, dp[i-2], num)
    return dp[len(arr)-1]

    Note that in the dp dictionary, we store the max sum for the subarray up till the length of the subarray. Hence, we simply return the last item in this dictionary to get the answer