Longest sub | C # implementation of th 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
using System ; using System . Collections . Generic ; class GFG { readonly static int N = 100 ; readonly static int INT_MIN = int . MinValue ; static int [ , ] dp = new int [ N , 3 ] ; static int [ , ] v = new int [ N , 3 ] ; static int findLargestString ( String s , int i , int r ) { if ( i == s . Length ) { if ( r == 0 ) return 0 ; else return INT_MIN ; } if ( v [ i , r ] == 1 ) return dp [ i , r ] ; v [ i , r ] = 1 ; dp [ i , r ] = Math . Max ( 1 + findLargestString ( s , i + 1 , ( r * 2 + ( s [ i ] - '0' ) ) % 3 ) , findLargestString ( s , i + 1 , r ) ) ; return dp [ i , r ] ; } public static void Main ( String [ ] args ) { String s = "101" ; Console . Write ( findLargestString ( s , 0 , 0 ) ) ; } }