Optimal strategy for a Game with modifications | Function to return sum of subarray from l to r ; calculate sum by a loop from l to r ; dp to store the values of sub problems ; if length of the array is less than k return the sum ; if the value is previously calculated ; else calculate the value ; select all the sub array of length len_r ; get the sum of that sub array ; check if it is the maximum or not ; store it in the table ; Driver code
function sum ( arr , l , r ) { let s = 0 ; for ( let i = l ; i <= r ; i ++ ) { s += arr [ i ] ; } return s ; } let dp = new Array ( 101 ) ; for ( let i = 0 ; i < 101 ; i ++ ) { dp [ i ] = new Array ( 101 ) ; for ( let j = 0 ; j < 101 ; j ++ ) { dp [ i ] [ j ] = new Array ( 101 ) ; for ( let k = 0 ; k < 101 ; k ++ ) { dp [ i ] [ j ] [ k ] = 0 ; } } } function solve ( arr , l , r , k ) { if ( r - l + 1 <= k ) return sum ( arr , l , r ) ; if ( dp [ l ] [ r ] [ k ] != 0 ) return dp [ l ] [ r ] [ k ] ; let sum_ = sum ( arr , l , r ) ; let len_r = ( r - l + 1 ) - k ; let len = ( r - l + 1 ) ; let ans = 0 ; for ( let i = 0 ; i < len - len_r + 1 ; i ++ ) { let sum_sub = sum ( arr , i + l , i + l + len_r - 1 ) ; ans = Math . max ( ans , ( sum_ - sum_sub ) + ( sum_sub - solve ( arr , i + l , i + l + len_r - 1 , k ) ) ) ; } dp [ l ] [ r ] [ k ] = ans ; return ans ; } let arr = [ 10 , 15 , 20 , 9 , 2 , 5 ] , k = 2 ; let n = arr . length ; document . write ( solve ( arr , 0 , n - 1 , k ) ) ;