Maximum score possible after performing given operations on an Array | Function to calculate maximum score recursively ; Base case ; Sum of array in range ( l , r ) ; If the operation is even - numbered the score is decremented ; Exploring all paths , by removing leftmost and rightmost element and selecting the maximum value ; Function to find the max score ; Prefix sum array ; Calculating prefix_sum ; Driver code
def maxScore ( l , r , prefix_sum , num ) : NEW_LINE INDENT if ( l > r ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( ( l - 1 ) >= 0 ) : NEW_LINE INDENT current_sum = ( prefix_sum [ r ] - prefix_sum [ l - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT current_sum = prefix_sum [ r ] - 0 NEW_LINE DEDENT if ( num % 2 == 0 ) : NEW_LINE INDENT current_sum *= - 1 ; NEW_LINE DEDENT return current_sum + max ( maxScore ( l + 1 , r , prefix_sum , num + 1 ) , maxScore ( l , r - 1 , prefix_sum , num + 1 ) ) ; NEW_LINE DEDENT def findMaxScore ( a , n ) : NEW_LINE INDENT prefix_sum = [ 0 ] * n NEW_LINE prefix_sum [ 0 ] = a [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT prefix_sum [ i ] = prefix_sum [ i - 1 ] + a [ i ] ; NEW_LINE DEDENT return maxScore ( 0 , n - 1 , prefix_sum , 1 ) ; NEW_LINE DEDENT n = 6 ; NEW_LINE A = [ 1 , 2 , 3 , 4 , 2 , 6 ] NEW_LINE ans = findMaxScore ( A , n ) NEW_LINE print ( ans ) NEW_LINE