Maximum sum in circular array such that no two elements are adjacent | Set 2 | C ++ program to find maximum sum in circular array such that no two elements are adjacent ; Store the maximum possible at each index ; When i exceeds the index of the last element simply return 0 ; If the value has already been calculated , directly return it from the dp array ; The next states are don 't take  this element and go to (i + 1)th state  else take this element  and go to (i + 2)th state ; function to find the max value ; subarr contains elements from 0 to arr . size ( ) - 2 ; Initializing all the values with - 1 ; Calculating maximum possible sum for first case ; subarr contains elements from 1 to arr . size ( ) - 1 ; Re - initializing all values with - 1 ; Calculating maximum possible sum for second case ; Printing the maximum between them ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > dp ; int maxSum ( int i , vector < int > & subarr ) { if ( i >= subarr . size ( ) ) return 0 ; if ( dp [ i ] != -1 ) return dp [ i ] ; return dp [ i ] = max ( maxSum ( i + 1 , subarr ) , subarr [ i ] + maxSum ( i + 2 , subarr ) ) ; } int Func ( vector < int > arr ) { vector < int > subarr = arr ; subarr . pop_back ( ) ; dp . resize ( subarr . size ( ) , -1 ) ; int max1 = maxSum ( 0 , subarr ) ; subarr = arr ; subarr . erase ( subarr . begin ( ) ) ; dp . clear ( ) ; dp . resize ( subarr . size ( ) , -1 ) ; int max2 = maxSum ( 0 , subarr ) ; cout << max ( max1 , max2 ) << endl ; } int main ( ) { vector < int > arr = { 1 , 2 , 3 , 1 } ; Func ( arr ) ; return 0 ; }