Maximum sum subarray after altering the array | Python3 implementation of the approach ; Function to return the maximum subarray sum ; Function to reverse the subarray arr [ 0. . . i ] ; Function to return the maximum subarray sum after performing the given operation at most once ; To store the result ; When no operation is performed ; Find the maximum subarray sum after reversing the subarray arr [ 0. . . i ] for all possible values of i ; The complete array is reversed so that the subarray can be processed as arr [ 0. . . i ] instead of arr [ i ... N - 1 ] ; Driver code
import sys NEW_LINE def maxSumSubarray ( arr , size ) : NEW_LINE INDENT max_so_far = - sys . maxsize - 1 NEW_LINE max_ending_here = 0 NEW_LINE for i in range ( size ) : NEW_LINE INDENT max_ending_here = max_ending_here + arr [ i ] NEW_LINE if ( max_so_far < max_ending_here ) : NEW_LINE INDENT max_so_far = max_ending_here NEW_LINE DEDENT if ( max_ending_here < 0 ) : NEW_LINE INDENT max_ending_here = 0 NEW_LINE DEDENT DEDENT return max_so_far NEW_LINE DEDENT def getUpdatedArray ( arr , copy , i ) : NEW_LINE INDENT for j in range ( ( i // 2 ) + 1 ) : NEW_LINE INDENT copy [ j ] = arr [ i - j ] NEW_LINE copy [ i - j ] = arr [ j ] NEW_LINE DEDENT return NEW_LINE DEDENT def maxSum ( arr , size ) : NEW_LINE INDENT resSum = - sys . maxsize - 1 NEW_LINE resSum = max ( resSum , maxSumSubarray ( arr , size ) ) NEW_LINE copyArr = [ ] NEW_LINE copyArr = arr NEW_LINE for i in range ( 1 , size , 1 ) : NEW_LINE INDENT getUpdatedArray ( arr , copyArr , i ) NEW_LINE resSum = max ( resSum , maxSumSubarray ( copyArr , size ) ) NEW_LINE DEDENT arr = arr [ : : - 1 ] NEW_LINE copyArr = arr NEW_LINE for i in range ( 1 , size , 1 ) : NEW_LINE INDENT getUpdatedArray ( arr , copyArr , i ) NEW_LINE resSum = max ( resSum , maxSumSubarray ( copyArr , size ) ) NEW_LINE DEDENT resSum += 6 NEW_LINE return resSum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ - 9 , 21 , 24 , 24 , - 51 , - 6 , 17 , - 42 , - 39 , 33 ] NEW_LINE size = len ( arr ) NEW_LINE print ( maxSum ( arr , size ) ) NEW_LINE DEDENT