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.
  • HackerRank Home
  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Interview Preparation Kit
  3. Dynamic Programming
  4. Max Array Sum

Max Array Sum

Problem
Submissions
Leaderboard
Discussions
Editorial

Given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset. It is possible that the maximum sum is , the case when all elements are negative.

Example

The following subsets with more than element exist. These exclude the empty subset and single element subsets which are also valid.

Subset      Sum
[-2, 3, 5]   6
[-2, 3]      1
[-2, -4]    -6
[-2, 5]      3
[1, -4]     -3
[1, 5]       6
[3, 5]       8

The maximum subset sum is . Note that any individual element is a subset as well.

In this case, it is best to choose no element: return .

Function Description

Complete the function in the editor below.

maxSubsetSum has the following parameter(s):

  • int arr[n]: an array of integers

Returns
- int: the maximum subset sum

Input Format

The first line contains an integer, .
The second line contains space-separated integers .

Constraints

Sample Input 0

5
3 7 4 6 5

Sample Output 0

13

Explanation 0

Our possible subsets are and . The largest subset sum is from subset

Sample Input 1

5
2 1 5 8 4

Sample Output 1

11

Explanation 1

Our subsets are and . The maximum subset sum is from the first subset listed.

Sample Input 2

5
3 5 -7 8 10

Sample Output 2

15

Explanation 2

Our subsets are and . The maximum subset sum is from the fifth subset listed.

Author

shashank21j

Difficulty

Medium

Max Score

20

Submitted By

80249

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Helpdesk
  • Careers
  • Terms Of Service
  • Privacy Policy

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website