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

|

492 Discussions

|

  • 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)

  • Shivam_purwar786
     + 0 comments

    def max_sum_non_adjacent(arr): if not arr: return 0 if len(arr) == 1: return arr[0]

    # Initialize prev2 (max sum until i-2) and prev1 (max sum until i-1)
prev2 = 0
prev1 = 0

# Traverse through the array
for num in arr:
    current = max(prev1, num + prev2)
    prev2 = prev1
    prev1 = current

return prev1

  • rmleon
     + 0 comments

    Space complexity O(1) and time complexity O(n) Many answers here have space complexity O(n)

    public static int maxSubsetSum(List<Integer> arr) {
    int valueMinus1 = 0;
    int valueMinus2 = 0;
    int sum = 0;
    for (int i = 0; i < arr.size(); i += 1) {
        if (arr.get(i) <= 0) {
            valueMinus1 = valueMinus2 = Math.max(valueMinus1, valueMinus2);
        } else {
            sum = Math.max(valueMinus1, arr.get(i) + valueMinus2);
            valueMinus2 = valueMinus1;
            valueMinus1 = sum;
        }
    }
    return sum;
}

  • dehaka
     + 0 comments

    very straightforward dynamic programming question, O(n)

    int maxSubsetSum(int n, const vector<int>& arr) {
    vector<int> cache(n);
    cache[0] = arr[0];
    cache[1] = max(arr[0], arr[1]);
    for (int i=2; i < n; ++i) cache[i] = max( {cache[i-1], cache[i-2] + arr[i], arr[i]} );
    return max(cache.back(), 0);
}