#include <stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int FindMaxSum(int arr[],int n)
{
int dp[n],final=0;
dp[0] = arr[0];
dp[1] = arr[1];
final = max(final,dp[0]);
final = max(final,dp[1]);
for(int i=2;i<n;i++)
{
dp[i] = max(dp[i-2]+ arr[i],arr[i]);
final = max(final,dp[i]);
}
return final;
}
int main()
{
int arr[] = {5, 5, 10, 100, 10, 5};
printf("%d \n", FindMaxSum(arr, 6));
getchar();
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlPGlvc3RyZWFtPgojaW5jbHVkZTxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBGaW5kTWF4U3VtKGludCBhcnJbXSxpbnQgbikKewoJaW50IGRwW25dLGZpbmFsPTA7CglkcFswXSA9IGFyclswXTsKCWRwWzFdID0gYXJyWzFdOwoJZmluYWwgPSBtYXgoZmluYWwsZHBbMF0pOwoJZmluYWwgPSBtYXgoZmluYWwsZHBbMV0pOwoJZm9yKGludCBpPTI7aTxuO2krKykKCXsKCQlkcFtpXSA9IG1heChkcFtpLTJdKyBhcnJbaV0sYXJyW2ldKTsKCQlmaW5hbCA9IG1heChmaW5hbCxkcFtpXSk7Cgl9CglyZXR1cm4gZmluYWw7Cn0KaW50IG1haW4oKQp7CiAgaW50IGFycltdID0gezUsIDUsIDEwLCAxMDAsIDEwLCA1fTsKICBwcmludGYoIiVkIFxuIiwgRmluZE1heFN1bShhcnIsIDYpKTsKICBnZXRjaGFyKCk7CiAgcmV0dXJuIDA7Cn0K