Maximum subsequence sum such that no three are consecutive in O ( 1 ) space | C ++ implementation for the above approach ; Function to calculate the maximum subsequence sum such that no three elements are consecutive ; when N is 1 , answer would be the only element present ; when N is 2 , answer would be sum of elements ; variable to store sum up to i - 3 ; variable to store sum up to i - 2 ; variable to store sum up to i - 1 ; variable to store the final sum of the subsequence ; find the maximum subsequence sum up to index i ; update first , second and third ; return ans ; ; Driver code ; Input ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSumWO3Consec ( int A [ ] , int N ) { if ( N == 1 ) return A [ 0 ] ; if ( N == 2 ) return A [ 0 ] + A [ 1 ] ; int third = A [ 0 ] ; int second = third + A [ 1 ] ; int first = max ( second , A [ 1 ] + A [ 2 ] ) ; int sum = max ( max ( third , second ) , first ) ; for ( int i = 3 ; i < N ; i ++ ) { sum = max ( max ( first , second + A [ i ] ) , third + A [ i ] + A [ i - 1 ] ) ; third = second ; second = first ; first = sum ; } return sum ; } int main ( ) { int A [ ] = { 3000 , 2000 , 1000 , 3 , 10 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << maxSumWO3Consec ( A , N ) ; return 0 ; }