Find maximum sum array of length less than or equal to m | N and M to define sizes of arr , dp , current_arr and maxSum ; INF to define min value ; Function to find maximum sum ; dp array of size N x M ; current_arr of size M ; maxsum of size M ; If we have 0 elements from 0 th array ; Compute the cumulative sum array ; Calculating the maximum contiguous array for every length j , j is from 1 to lengtn of the array ; Every state is depending on its previous state ; computation of dp table similar approach as knapsack problem ; Now we have done processing with the last array lets find out what is the maximum sum possible ; Driver code ; First element of each row is the size of that row
N = 105 NEW_LINE M = 1001 NEW_LINE INF = - 1111111111 NEW_LINE def maxSum ( arr ) : NEW_LINE INDENT dp = [ [ - 1 for x in range ( M ) ] for y in range ( N ) ] NEW_LINE current_arr = [ 0 ] * M NEW_LINE maxsum = [ 0 ] * M NEW_LINE current_arr [ 0 ] = 0 NEW_LINE dp [ 0 ] [ 0 ] = 0 NEW_LINE for i in range ( 1 , 6 ) : NEW_LINE INDENT len = arr [ i - 1 ] [ 0 ] NEW_LINE for j in range ( 1 , len + 1 ) : NEW_LINE INDENT current_arr [ j ] = arr [ i - 1 ] [ j ] NEW_LINE current_arr [ j ] += current_arr [ j - 1 ] NEW_LINE maxsum [ j ] = INF NEW_LINE DEDENT j = 1 NEW_LINE while j <= len and j <= 6 : NEW_LINE INDENT for k in range ( 1 , len + 1 ) : NEW_LINE INDENT if ( j + k - 1 <= len ) : NEW_LINE INDENT maxsum [ j ] = max ( maxsum [ j ] , current_arr [ j + k - 1 ] - current_arr [ k - 1 ] ) NEW_LINE DEDENT DEDENT j += 1 NEW_LINE DEDENT for j in range ( 7 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE DEDENT for j in range ( 1 , 7 ) : NEW_LINE INDENT cur = 1 NEW_LINE while cur <= j and cur <= len : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j - cur ] + maxsum [ cur ] ) NEW_LINE cur += 1 NEW_LINE DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 7 ) : NEW_LINE INDENT ans = max ( ans , dp [ 5 ] [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 3 , 2 , 3 , 5 ] , [ 2 , 7 , - 1 ] , [ 2 , 8 , 10 ] , [ 4 , 5 , 2 , 6 , 1 ] , [ 3 , 2 , 3 , - 2 ] ] NEW_LINE print ( " Maximum ▁ sum ▁ can ▁ be ▁ obtained " , " is ▁ : ▁ " , maxSum ( arr ) ) NEW_LINE DEDENT