Max Array Sum Discussions |

Sort 476 Discussions, By:

2 weeks ago+ 0 comments

Python:

from collections import deque


def maxSubsetSum(arr):

    final_sums= arr[:2] + [max([arr[0],0]) + max([arr[2],0])]
    final_sums = deque(final_sums)
    for n, i in enumerate(arr[3:]):
        i = max([i,0])
        new_max = max(final_sums[0] + i, final_sums[1] + i)
        final_sums.rotate(-1)
        final_sums[2] = new_max   
        
    return max(final_sums)

3 weeks ago+ 0 comments

Java:

int maxSubsetSum(int[] arr) {
        if (arr == null || arr.length == 0) return -1;
        int dp[] = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        
        for (int i = 2; i < arr.length; i++) {
            int sum = arr[i] + dp[i-2];
            dp[i] = Math.max(Math.max(sum, dp[i-1]), arr[i]);
        }
        
        return dp[arr.length - 1];
    }

1 month ago+ 0 comments

Python:

def maxSubsetSum(arr):
    res = [arr[-1],arr[-2]]
    for i in range(len(arr)-3,-1,-1):
            tmp = max(res[:-1])
            if arr[i]+tmp > arr[i]:
                res = [tmp,res[-1]]
                res.append(res[0]+arr[i])
            else:
                res.append(arr[i])

    return max(res)

1 month ago+ 0 comments

In Swift

func maxSubsetSum(arr: [Int]) -> Int {
        var maxSums = [Int](repeating: 0, count: arr.count)

        for i in 0..<arr.count {
                var first = max(arr[i], 0)
                var second = 0
                var third = 0

                if i >= 2 {
                        second = maxSums[i - 2]
                } else {
                        second = 0
                }

                if i >= 1 {
                        third = maxSums[i - 1]
                } else {
                        third = 0
                }

                maxSums[i] = max(first + second, third)
        }

        var total = max(maxSums[arr.count - 1], maxSums[arr.count - 2])
        print(total)
        return total 
}

1 month ago+ 0 comments

Java - Recursive Solution with memoization:

static int maxSubsetSum(int[] arr) {
        Integer[] memo = new Integer[arr.length];
        return maxSum(0, arr, memo);
    }

    private static int maxSum(int i, int[] arr, Integer[] memo) {
        if (i >= arr.length) {
            return 0;
        }
        if (memo[i] != null) {
            return memo[i];
        }
        memo[i] = Math.max(arr[i] + maxSum(i + 2, arr, memo), maxSum(i + 1, arr, memo)); 
        return memo[i];
    }

Load more conversations