Maximum subarray sum in O ( n ) using prefix sum | Python3 program to find out maximum subarray sum in linear time using prefix sum . ; Function to compute maximum subarray sum in linear time . ; Initialize minimum prefix sum to 0. ; Initialize maximum subarray sum so far to - infinity . ; Initialize and compute the prefix sum array . ; loop through the array keep track of minimum prefix sum so far and maximum subarray sum . ; Test case 1 ; Test case 2
import math NEW_LINE def maximumSumSubarray ( arr , n ) : NEW_LINE INDENT min_prefix_sum = 0 NEW_LINE res = - math . inf NEW_LINE prefix_sum = [ ] NEW_LINE prefix_sum . append ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT prefix_sum . append ( prefix_sum [ i - 1 ] + arr [ i ] ) NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT res = max ( res , prefix_sum [ i ] - min_prefix_sum ) NEW_LINE min_prefix_sum = min ( min_prefix_sum , prefix_sum [ i ] ) NEW_LINE DEDENT return res NEW_LINE DEDENT arr1 = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ] NEW_LINE n1 = len ( arr1 ) NEW_LINE print ( maximumSumSubarray ( arr1 , n1 ) ) NEW_LINE arr2 = [ 4 , - 8 , 9 , - 4 , 1 , - 8 , - 1 , 6 ] NEW_LINE n2 = len ( arr2 ) NEW_LINE print ( maximumSumSubarray ( arr2 , n2 ) ) NEW_LINE