Optimal strategy for a Game with modifications | Python3 implementation of the above approach ; 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
import numpy as np NEW_LINE def Sum ( arr , l , r ) : NEW_LINE INDENT s = 0 ; NEW_LINE for i in range ( l , r + 1 ) : NEW_LINE INDENT s += arr [ i ] ; NEW_LINE DEDENT return s ; NEW_LINE DEDENT dp = np . zeros ( ( 101 , 101 , 101 ) ) ; NEW_LINE def solve ( arr , l , r , k ) : NEW_LINE INDENT if ( r - l + 1 <= k ) : NEW_LINE INDENT return Sum ( arr , l , r ) ; NEW_LINE DEDENT if ( dp [ l ] [ r ] [ k ] ) : NEW_LINE INDENT return dp [ l ] [ r ] [ k ] ; NEW_LINE DEDENT sum_ = Sum ( arr , l , r ) ; NEW_LINE len_r = ( r - l + 1 ) - k ; NEW_LINE length = ( r - l + 1 ) ; NEW_LINE ans = 0 ; NEW_LINE for i in range ( length - len_r + 1 ) : NEW_LINE INDENT sum_sub = Sum ( arr , i + l , i + l + len_r - 1 ) ; NEW_LINE ans = max ( ans , ( sum_ - sum_sub ) + ( sum_sub - solve ( arr , i + l , i + l + len_r - 1 , k ) ) ) ; NEW_LINE DEDENT dp [ l ] [ r ] [ k ] = ans ; NEW_LINE return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 10 , 15 , 20 , 9 , 2 , 5 ] ; k = 2 ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( solve ( arr , 0 , n - 1 , k ) ) ; NEW_LINE DEDENT