This is a popular problem with DP. I have to find the maximum sum in an array which is formed by non-adjacent elements only. I saw other posts but I want to do this using dynamic programming, in particular, bottom-up DP. Here is my code:
int maxSubsetSum(vector<int> arr,int start,int end) {
int sum[arr.size()]; //to store max sum upto a given index
sum[0] = arr[start];
sum[1] = max(arr[start], arr[end]);
if(start==end){
return sum[0];
}
else if(start==end-1){
return sum[1];
}
else{
for(int i=2;i<=end;i++){
sum[i]=max(arr[i],max(arr[i]+sum[i-2],sum[i-1]));
}
}
return sum[end];
}
I am running into errors passing the test cases. Although when I ran one test case by hand it worked out correctly. The actual output was the same as what I had obtained. But the testing system gave a different output to my code.
I tested this code by hand on test case: 3 5 -7 8 10 and the answer matched the actual output (=15) but test case did not pass.
sum[0]=3
sum[1]=5
sum[2]=max(-7,max(-7+3,5))=5
sum[3]=max(8,max(8+5,5))=13
sum[4]=max(10,max(10+5,13))=15
Please point me in the right direction where I am doing wrong.
Try this:
int maxSubsetSum(vector<int> arr) {
if (arr.size() == 1) {
return arr[0];
}
if (arr.size() == 2) {
return max(arr[0], arr[1]);
}
int sum[arr.size()]; //to store max sum upto a given index
sum[0] = arr[0];
sum[1] = max(arr[0], arr[1]);
for(int i = 2; i < arr.size(); i++) {
sum[i] = max(arr[i], max(arr[i] + sum[i - 2], sum[i - 1]));
}
return sum[arr.size() - 1];
}