The following code doesn't correctly return the index values of the minimum contiguous subsequence. Please modify it so that it does, with comments if possible. def minSumRec(a, left, right): if left == right: return [a[left], left, right] center = int((left + right) / 2) min_left_sum = minSumRec(a, left, center) min_right_sum = minSumRec(a, center + 1, right) min_left_border_sum, left_border_sum = 1e9, 0 for i in range(center, left - 1, -1): left_border_sum += a[i] if left_border_sum < min_left_border_sum: min_left_border_sum = left_border_sum min_right_border_sum, right_border_sum = 1e9, 0 for i in range(center + 1, right + 1): right_border_sum += a[i] if right_border_sum < min_right_border_sum: min_right_border_sum = right_border_sum min_border_sum = min_right_border_sum + min_left_border_sum minSum = min(min_left_sum[0], min_right_sum[0], min_border_sum) if minSum == min_left_sum: return min_left_sum if minSum == min_right_sum: return min_right_sum return [min_border_sum, left + 1, right - 1]
The following code doesn't correctly return the index values of the minimum contiguous subsequence. Please modify it so that it does, with comments if possible.
def minSumRec(a, left, right):
if left == right:
return [a[left], left, right]
center = int((left + right) / 2)
min_left_sum = minSumRec(a, left, center)
min_right_sum = minSumRec(a, center + 1, right)
min_left_border_sum, left_border_sum = 1e9, 0
for i in range(center, left - 1, -1):
left_border_sum += a[i]
if left_border_sum < min_left_border_sum:
min_left_border_sum = left_border_sum
min_right_border_sum, right_border_sum = 1e9, 0
for i in range(center + 1, right + 1):
right_border_sum += a[i]
if right_border_sum < min_right_border_sum:
min_right_border_sum = right_border_sum
min_border_sum = min_right_border_sum + min_left_border_sum
minSum = min(min_left_sum[0], min_right_sum[0], min_border_sum)
if minSum == min_left_sum:
return min_left_sum
if minSum == min_right_sum:
return min_right_sum
return [min_border_sum, left + 1, right - 1]
Step by step
Solved in 3 steps with 1 images