Longest sub | C ++ implementation of the approach ; Function to return the length of the largest sub - string divisible by 3 ; Base - case ; If the state has been solved before then return its value ; Marking the state as solved ; Recurrence relation ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100 NEW_LINE int dp [ N ] [ 3 ] ; bool v [ N ] [ 3 ] ; int findLargestString ( string & s , int i , int r ) { if ( i == s . size ( ) ) { if ( r == 0 ) return 0 ; else return INT_MIN ; } if ( v [ i ] [ r ] ) return dp [ i ] [ r ] ; v [ i ] [ r ] = 1 ; dp [ i ] [ r ] = max ( 1 + findLargestString ( s , i + 1 , ( r * 2 + ( s [ i ] - '0' ) ) % 3 ) , findLargestString ( s , i + 1 , r ) ) ; return dp [ i ] [ r ] ; } int main ( ) { string s = "101" ; cout << findLargestString ( s , 0 , 0 ) ; return 0 ; }