loading...

Daily HackerRank Challenge - Day 23

wingkwong profile image Wing-Kam ・2 min read

About

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


Max Array Sum

image

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[0] and arr[1]. To do so, we create an array dp with the size same as arr to store the maximum sum at index i.

dp[0]=arr[0];
dp[1]=max(arr[0],arr[1]);

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[0];
    int dp[sz];
    dp[0]=arr[0];
    dp[1]=max(arr[0],arr[1]);
    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

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

pic
Editor guide