Maximize occurrences of values between L and R on sequential addition of Array elements with modulo H | C ++ implementation of the above approach ; Function that prints the number of times X gets a value between L and R ; Base condition ; Condition if X can be made equal to j after i additions ; Compute value of X after adding arr [ i ] ; Compute value of X after adding arr [ i ] - 1 ; Update dp as the maximum value ; Compute maximum answer from all possible cases ; Printing maximum good occurrence of X ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void goodInteger ( int arr [ ] , int n , int h , int l , int r ) { vector < vector < int > > dp ( n + 1 , vector < int > ( h , -1 ) ) ; dp [ 0 ] [ 0 ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < h ; j ++ ) { if ( dp [ i ] [ j ] != -1 ) { int h1 = ( j + arr [ i ] ) % h ; int h2 = ( j + arr [ i ] - 1 ) % h ; dp [ i + 1 ] [ h1 ] = max ( dp [ i + 1 ] [ h1 ] , dp [ i ] [ j ] + ( h1 >= l && h1 <= r ) ) ; dp [ i + 1 ] [ h2 ] = max ( dp [ i + 1 ] [ h2 ] , dp [ i ] [ j ] + ( h2 >= l && h2 <= r ) ) ; } } } int ans = 0 ; for ( int i = 0 ; i < h ; i ++ ) { if ( dp [ n ] [ i ] != -1 ) ans = max ( ans , dp [ n ] [ i ] ) ; } cout << ans << " STRNEWLINE " ; } int main ( ) { int A [ ] = { 16 , 17 , 14 , 20 , 20 , 11 , 22 } ; int H = 24 ; int L = 21 ; int R = 23 ; int size = sizeof ( A ) / sizeof ( A [ 0 ] ) ; goodInteger ( A , size , H , L , R ) ; return 0 ; }