Maximum Non-Contiguous Sum of a Series

Given an arbitrary series, we've to calculate the maximum sum confined to only one restriction-
If we choose any number a [ i ] to calculate the sum, we can't choose a [ i+1 ]
Let's take a series: a[ ]= {1,2,3,4,5,9}

Linear Solution: Take two variable inc and exl. inc will store value if we choose a [ i ] to calculate the sum & exl will store value if we do not choose a [ i ], for any 0 ≤ i ≤ n. Now for every step, we have to calculate inc and exl. After iteration ends, max( inc,exl ) is the maximum non-contiguous sum. Roughly-

	for(int i=0; i<m; i++)
	{
	scanf("%d",&x);
	if(i==0)
	{
	inc= x;
	exl= 0;
	}
	else
	temp=exl;
	exl = max(inc,exl);
	inc = temp + x;
	}
	}
	print: max(inc,exl)

view raw MaximumNonContiguousSumSnippet.cpp hosted with ❤ by GitHub

Why inc = exl + a [ i ] ? because the already calculated exl is from i-2. So if we choosed inc=  inc + a [ i ] , that would be a contiguous sum. exl is maximum of inc & exl right until  i-1.
Top Down solution( DP ): If you're familiar with dynamic programming, you know that, we need to calculate dp[n] - the maximum non contiguous sum at nth index.
Now we can have two possible state, we'll select the maximum one.
dp[ i ] = a [ i ] + dp [ i-2 ]   choosing i'th value
dp[ i ] = a [ i-1 ] + dp [ i-3 ]  choosing the value before i'th

	#include<stdio.h>
	#include<algorithm>
	using namespace std;
	int dp[10000],ar[10000];
	int mncs(int n)
	{
	if(n<0) return 0;
	if(dp[n]!=0) return dp[n];
	dp[n] = max({ (ar[n] + mncs(n-2)), (ar[n-1]+ mncs(n-3) ) });
	return dp[n];
	}
	int main()
	{
	int i,t,x;
	while(1)
	{
	scanf("%d",&x);
	for(i=0;i<x;i++)
	{
	scanf("%d",&ar[i]);
	}
	printf("%d\n",mncs(x-1));
	free(dp);
	free(ar);
	}
	}

view raw MaximumNonContiguousSumDP.cpp hosted with ❤ by GitHub