Maximum number of segments of lengths a , b and c | C ++ implementation to divide N into maximum number of segments of length a , b and c ; function to find the maximum number of segments ; stores the maximum number of segments each index can have ; initialize with - 1 ; 0 th index will have 0 segments base case ; traverse for all possible segments till n ; conditions if ( i + a <= n ) avoid buffer overflow ; if ( i + b <= n ) avoid buffer overflow ; if ( i + c <= n ) avoid buffer overflow ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumSegments ( int n , int a , int b , int c ) { int dp [ n + 1 ] ; memset ( dp , -1 , sizeof ( dp ) ) ; dp [ 0 ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( dp [ i ] != -1 ) { dp [ i + a ] = max ( dp [ i ] + 1 , dp [ i + a ] ) ; dp [ i + b ] = max ( dp [ i ] + 1 , dp [ i + b ] ) ; dp [ i + c ] = max ( dp [ i ] + 1 , dp [ i + c ] ) ; } } return dp [ n ] ; } int main ( ) { int n = 7 , a = 5 , b = 2 , c = 5 ; cout << maximumSegments ( n , a , b , c ) ; return 0 ; }