这是 DP 的一个普遍问题。我必须在仅由非相邻元素形成的数组中找到最大和。我看到了其他帖子,但我想使用动态编程来做到这一点,特别是自下而上的 DP。这是我的代码:
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];
}
我在通过测试用例时遇到错误。尽管当我手动运行一个测试用例时,它的结果是正确的。实际输出与我获得的相同。但是测试系统给我的代码提供了不同的输出。
我在测试用例上手动测试了这段代码:3 5 -7 8 10,答案与实际输出匹配(=15),但测试用例没有通过。
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
请指出我做错的正确方向。