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

|

491 Discussions

|

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

  • vellavarun
     + 0 comments

    Solution: we start from the last element and we try to see if that element belongs to the max subset group. There can be 4 scenarios: * element belongs * adjancent elements belongs instead * element belongs with non-adjacent element * non-adjacebnt elemnt belongs instead * none belong, but that can be taken care of by making it recursively check what's best for the next step. Here's the code:

    # n <= 10^5
sys.setrecursionlimit(100000)

# Complete the maxSubsetSum function below.
def maxSubsetSum(arr):
    
    # for memoization
    cache = {}
    
    # subfunction for finding the right path
    def max_subarr(position):
        if position in cache:
            return cache[position]
        result = 0
        if position < 0:
            return result
        else:
            # choose the maximum between:
            # self, self + (non-adjacent next), adjacent next, non-adjacent next
            result = max(arr[position],
                        arr[position] + max_subarr(position-2),
                        max_subarr(position-1),
                        max_subarr(position-2))
        
        # print("position %s result %s" % (position, result))
        
        # cache for memoization
        cache[position] = result
        
        return result
        
    maxSubSum = max_subarr(len(arr)-1)
    return maxSubSum