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

Sort by

recency

|

495 Discussions

|

  • pius_krisantono
     + 0 comments

    Solution with Java 8 using Map. Is it good or bad?

    public class Solution {
    
    static Map<Integer, Integer> indexMaxValueMap = new HashMap<>();

    static int maxSubsetSum(int[] arr, int currentIndex) {
        if (currentIndex > arr.length - 1) {
            return 0;
        }
        
        if (indexMaxValueMap.get(currentIndex) != null) {
            return indexMaxValueMap.get(currentIndex);
        }
        
        int currentValue = Math.max(0, arr[currentIndex]);
        
        currentValue += Math.max(maxSubsetSum(arr, currentIndex + 2), maxSubsetSum(arr, currentIndex + 3));
        
        indexMaxValueMap.put(currentIndex, currentValue);
        
        return currentValue;
    }

    static int maxSubsetSum(int[] arr) {
        return Math.max(maxSubsetSum(arr, 0), maxSubsetSum(arr, 1));
    }

  • wdkaye
     + 1 comment

    I finally had success with a recursive solution in C++11. It does do some repetitive work and could probably be made more efficient.

    Basically, it picks a cell in the middle of the range of length n; n/2 == k. * First it assumes that arr[k] isn't part of the solution, and it solves recursively for the ranges on either side of that cell [0, k-1] and [k+1,n] and returns the sum. * If arr[k] is positive, then it might be part of the solution, so it also solves recursively for [0, k-2], [k+2, n], adding arr[k] to the new sum. If that sum is higher than the previous sum, then it returns that valueinstead.

  • jono_reshef
     + 0 comments

    Bumping the solution from about 6 years ago, Python3

    def maxSubsetSum(coll):
    a,b = -math.inf,-math.inf
    for val in coll:
        a,b = b, max(a, a + val, b, val) 
    return b

  • tan_191
     + 0 comments

    Java 8 solution (passes all test cases):

        static int maxSubsetSum(int[] arr) {
        int[] dynArray = new int[arr.length + 1];
        dynArray[0] = 0;
        dynArray[1] = arr[0];
        List<Integer> toCompare = new ArrayList<Integer>();
        
        for (int i = 2; i <= arr.length; i++) {
            toCompare = new ArrayList<Integer>();
            toCompare.add(dynArray[i-1]);
            toCompare.add(arr[i-1]);
            toCompare.add(dynArray[i-2] + arr[i-1]);
            dynArray[i] = Collections.max(toCompare);
        }
        
        Arrays.sort(dynArray);
        
        return Math.max(dynArray[arr.length],0);
    }

  • matheushsoaress
     + 0 comments

    Using an additional array

    def maxSubsetSum(arr):
    L = [0] * (len(arr) + 1)
    L[1] = arr[0]
    
    for i in range(2, len(L)):
        L[i] = max(L[i-1], arr[i-1], arr[i-1]+L[i-2])
    return max(L)