FARIDA - Princess Farida Editorial - UCS

                                            FARIDA - Princess Farida

The link to the problem FARIDA - Princess Farida :

http://www.spoj.com/problems/FARIDA/

This is a dynamic programming problem. To simply describe the problem you have to select the index elements of an array that are not adjacent to each other. So as to make the maximum sum of selected indexes values of the array.

The CPP solution for the problem  ARIDA - Princess Farida  is

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long  int a[10005],dp[10005];
long long int n;

long long int sol(long long int i)
{
      if(i>=n)
      return 0;
      if(i==n-1)
      return a[n-1];
      if(dp[i]!=-1)
      return dp[i];
      dp[i]=max((a[i]+sol(i+2)),sol(i+1));
      return dp[i];
}

int main() {
 int i,j,k,t;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
      scanf("%lld",&n);
      for(j=0;j<n;j++)
      scanf("%lld",&a[j]);
      memset(dp,-1,sizeof dp);
printf("Case %d: %lld\n",i,sol(0));
}
 return 0;
}

Happy Coding.............