#include<stdio.h>
int max(int a,int b)
{
return a>b?a:b;
}
/*Function to retn max sum such that no two elements
are adjacent */
int FindMaxSum(int arr[], int n)
{
int dp[n];
int i;
dp[0]=arr[0];
dp[1]=max(arr[0],arr[1]);
for(i=2;i<n;i++)
{
dp[i]=max(arr[i]+dp[i-2],max(dp[i-1],arr[i]));
}
return dp[n-1];
}
/* Driver program to test above function */
int main()
{
int arr[] = {-3 ,-2 ,-1 ,-10};
printf("%d \n", FindMaxSum
(arr
, 4)); return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KIAppbnQgbWF4KGludCBhLGludCBiKQp7CiAgICByZXR1cm4gYT5iP2E6YjsKfQovKkZ1bmN0aW9uIHRvIHJldG4gbWF4IHN1bSBzdWNoIHRoYXQgbm8gdHdvIGVsZW1lbnRzCiBhcmUgYWRqYWNlbnQgKi8KaW50IEZpbmRNYXhTdW0oaW50IGFycltdLCBpbnQgbikKewogICAgaW50IGRwW25dOwogICAgaW50IGk7CiAgICBkcFswXT1hcnJbMF07CiAgICBkcFsxXT1tYXgoYXJyWzBdLGFyclsxXSk7CiAgICBmb3IoaT0yO2k8bjtpKyspCiAgICB7CiAgICAgICAgICAgICAgICAgICAgZHBbaV09bWF4KGFycltpXStkcFtpLTJdLG1heChkcFtpLTFdLGFycltpXSkpOwogICAgfQogICAgcmV0dXJuIGRwW24tMV07Cn0KIAovKiBEcml2ZXIgcHJvZ3JhbSB0byB0ZXN0IGFib3ZlIGZ1bmN0aW9uICovCmludCBtYWluKCkKewogIGludCBhcnJbXSA9IHstMyAsLTIgLC0xICwtMTB9OwogIHByaW50ZigiJWQgXG4iLCBGaW5kTWF4U3VtKGFyciwgNCkpOwogIGdldGNoYXIoKTsKICByZXR1cm4gMDsKfQo=