Maximum subarray problem
The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array, a[1...n], of numbers which has the largest sum. The list usually contains both positive and negative numbers along with 0. For example, for the array [−2, 1, −3, 4, −1, 2, 1, −5, 4] the contiguous subarray with the largest sum is [4, −1, 2, 1], with sum 6.
Solutions
Dynamic Programming
Implementation
class MaximumSubarray:
def solve(self, array):
sum_list = [array[0]]
start_idx = 0
for i in range(1, len(array)):
ele = array[i]
addup = sum_list[-1] + ele
sum_list.append(max(ele, addup))
if ele > addup: start_idx = i
max_sum = max(sum_list)
end_idx = len(sum_list) - 1 - sum_list[::-1].index(max_sum)
print(array[start_idx:end_idx+1])
return max_sum