We can have an application for finding the lists with the maximum value and printing it. This seems quite an easy task and may also be easy to code, but having shorthands to perform the same is always helpful as this kind of problem can come in web development. In this article, we will see a different technique to maximize the sum sublist in Python.
Method 1: Using reduce() + lambda
The above two functions can help us achieve this particular task. The lambda function does the task of logic and iteration and Reduce() function does the task of returning the required result. Works in Python 2 only.
Python
# Python code to demonstrate# maximum sum sublist # using reduce() + lambda# importing functools for reduce()import functools# initializing matrix test_matrix = [[1, 3, 1], [4, 5, 3], [1, 2, 4]]# printing the original matrixprint ("The original matrix is : " + str(test_matrix))# using reduce() + lambda# maximum sum sublist res = functools.reduce(lambda i, j: i if sum(i) > sum(j) else j, test_matrix)# printing resultprint ("Maximum sum sublist is : " + str(res)) |
The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]] Maximum sum sublist is : [4, 5, 3]
Time complexity: O(M^N) as the number of combinations generated is M choose N.
Auxiliary space: O(M^N) as the size of the resultant list is also M choose N.
Method 2: Using max() + key
The max() function can get the maximum of all the lists and the key is used to specify what the max condition has to be applied that is summation in this case.
Python3
# Python3 code to demonstrate# maximum sum sublist # using max() + key# initializing matrix test_matrix = [[1, 3, 1], [4, 5, 3], [1, 2, 4]]# printing the original matrixprint ("The original matrix is : " + str(test_matrix))# using max() + key# maximum sum sublist res = max(test_matrix, key = sum)# printing resultprint ("Maximum sum sublist is : " + str(res)) |
The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]] Maximum sum sublist is : [4, 5, 3]
Time complexity: O(n), where n is length of test_matrix
Space Complexity: O(n), where n is the length of the res list.
Method 3: Dynamic programming approach
The idea of the above dynamic programming approach is to use a 1D array dp to store the maximum sum subarray ending at each element of a particular row of the given matrix. We initialize dp with the first row of the matrix, and then for each subsequent row, we update the dp array by considering the maximum sum subarray that can be formed by adding the current row to the previous row’s maximum sum subarray. We also keep track of the maximum sum seen so far and the row index of that maximum sum.
At the end of the algorithm, the maximum sum sublist would be the row whose index was stored earlier as having the maximum sum.
Python3
# Python code to demonstrate# maximum sum sublist# using dynamic programming# initializing matrixtest_matrix = [[1, 3, 1], [4, 5, 3], [1, 2, 4]]# printing the original matrixprint("The original matrix is : " + str(test_matrix))# using dynamic programming# maximum sum sublistdp = test_matrix[0]max_sum = sum(dp)max_row = 0for i in range(1, len(test_matrix)): for j in range(len(test_matrix[0])): if j == 0: dp[j] = test_matrix[i][j] else: dp[j] = max(dp[j-1], 0) + test_matrix[i][j] if dp[j] > max_sum: max_sum = dp[j] max_row = ires = test_matrix[max_row]# printing resultprint("Maximum sum sublist is : " + str(res)) |
The original matrix is: [[1, 3, 1], [4, 5, 3], [1, 2, 4]] Maximum sum sublist is: [[1, 3, 1], [4, 5, 3], [1, 2, 4]]
Time complexity: O(mn), where m is the number of rows and n is the number of columns in the matrix.
Auxiliary space: O(n), where n is the number of columns in the matrix.
Method 4: Brute force approach
- Initialize a variable max_sum to negative infinity.
- Initialize two variables start_index and end_index to 0.
- Loop over all possible sublists of the input list test_matrix using two nested loops:
a. Compute the sum of the current sublist.
b. If the sum is greater than max_sum, update max_sum, start_index, and end_index to the current sum, start index, and end index respectively. - Return the sublist of test_matrix from start_index to end_index.
Python3
# Python3 code to demonstrate# maximum sum sublist # using brute force# initializing matrix test_matrix = [[1, 3, 1], [4, 5, 3], [1, 2, 4]]# printing the original matrixprint ("The original matrix is : " + str(test_matrix))# using brute force# maximum sum sublist n = len(test_matrix)max_sum = float('-inf')start_index = end_index = 0for i in range(n): for j in range(i, n): sublist_sum = sum(test_matrix[i][k] for k in range(j+1)) if sublist_sum > max_sum: max_sum = sublist_sum start_index, end_index = i, j# printing resultres = test_matrix[start_index][:(end_index+1)]print ("Maximum sum sublist is : " + str(res)) |
The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]] Maximum sum sublist is : [4, 5, 3]
The time complexity of this approach is O(n^3) because of the nested loops, where n is the length of the input list.
The auxiliary space complexity is O(1) because we are only storing a few variables.
