# Daily HackerRank Challenge - Day 23

This is a series of Daily HackerRank Challenge. Each day I show the some solutions written in C++.

# Max Array Sum Sample Input

``````5
3 7 4 6 5
``````

Sample Output 0

``````13
``````

First we should think about the base cases. Given that the minimum value is 1, we can return the first element if n is 1. If n is 2, we pick the maximum sum from `arr` and `arr`. To do so, we create an array `dp` with the size same as `arr` to store the maximum sum at index `i`.

``````dp=arr;
dp=max(arr,arr);
``````

Starting from the third element, we either pick

• the current value only (which is greater than the previous accumlated sum)
• the previous value only (which is greater than the current value and its previous value)
• the second previous value plus the current value (because we cannot sum adjacent elements)
``````dp[i] = max({dp[i-1], arr[i],dp[i-2]+arr[i]});
``````

At the end, return `dp[sz-1]` which is our maximum sum.

Final Solution

``````int maxSubsetSum(vector<int> arr) {
int sz = (int) arr.size();
if(!sz) return 0;
if (sz==1) return arr;
int dp[sz];
dp=arr;
dp=max(arr,arr);
for(int i=2;i<sz;i++){
dp[i] = max({dp[i-1], arr[i],dp[i-2]+arr[i]});
}
return dp[sz-1];
}
``````

# Complete Code

Check out the complete code via below link

### Discussion   