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.

- Max Array Sum
- Discussions

# Max Array Sum

# Max Array Sum

+ 0 comments

+ 1 comment Simple Python Solution - fully commented and easy to understand, also takes into account 1 element case (test cases don't cover this):

def maxSubsetSum(arr): length = len(arr) # Initialize a solution array (dp) to store the solution # to the problem for numbers from index 0 to index i # at dp[i] dp = [0] * length # Initialize dp[0] as the first element of the array (or 0) if it is negative dp[0] = max(arr[0], 0) # Stop and return dp[0] if the length of the array is 1 if length == 1: return dp[0] # Initialize dp[1] as the max of the first element, second element (or 0) dp[1] = max(dp[0], arr[1]) # Set dp[1] to the maximum of the previous solution or 2 solutions back + the # current value in the array (disallowing adjacent elements to be added to the set) for i in range(2, length): dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]) # Returning the solution for the whole array (as the last element in the dp array) return dp[-1]

+ 0 comments C#

static int maxSubsetSum(int[] arr) { for(var i = 2; i < arr.Length; i++){ arr[i-1] = Math.Max(arr[i-1], arr[i-2]); arr[i] = Math.Max(arr[i], Math.Max(arr[i-2], arr[i] + arr[i-2])); } return Math.Max(arr[arr.Length - 1], arr[arr.Length - 2]); }

+ 0 comments Here is a node solution. I tried to make it as readable as possible: For Dynamic Programmin, you want to keep track of the base cases before you start looping. During your looping, you still want to keep track of what you are looking for on each index so that the later indexes can access them without needing to do recalculations. It is crutial to do as little calculations as possible. Take a look:

function maxSubsetSum(arr) { let pointerIndex = 2; let maxSubsetSum = Math.max(arr[0], arr[1]); let positionMaxes = { 0: arr[0], 1: Math.max(arr[1], arr[0]), }; while(pointerIndex < arr.length) { if(positionMaxes[pointerIndex]) { pointer++; } positionMaxes[pointerIndex] = Math.max(arr[pointerIndex], positionMaxes[pointerIndex-2] + arr[pointerIndex], maxSubsetSum) maxSubsetSum = Math.max(maxSubsetSum, positionMaxes[pointerIndex]) pointerIndex++; } return maxSubsetSum; }

+ 1 comment Simple Java Solution

static int maxSubsetSum(int[] arr) { int a=arr[0]; int b=0; for(int i=1;i<arr.length;i++) { int temp=a; a=b+arr[i]; b=(int)Math.max(temp,b); } return (int)Math.max(a,b); }

Load more conversations

Sort 483 Discussions, By:

Please Login in order to post a comment