I am solving this problem using Python, and I don\'t really know how to do the s

Question

I am solving this problem using Python, and I don't really know how to do the second question!!!! I have my code at the bottom, please continue with my code and solve question 2(if possible, question3 as well)!!! Thx!!!!

def segmentMax(alist):
if len(alist) <2:
return sum(alist)
else:
midpoint=len(alist)//2
segment1=segmentMax(alist[:midpoint])
segment2=segmentMax(alist[midpoint:])
segment3=midmax(alist)
return max(segment1,segment2,segment3)
def midmax(alist):
rightmost = 0
leftmost= 0
sum1=0
sum2=0
midpoint=len(alist)//2
for i in range(midpoint):
sum1 = sum1+ alist[midpoint+i]
if sum1>rightmost:
rightmost=sum1
  
for i in range(midpoint):
sum2 = sum2+alist[midpoint-i-1]
if sum2>leftmost:
leftmost=sum2

return leftmost+rightmost

maxsum = [-8,4,-2,5,7,-8,19,-3,0,1]   
print(segmentMax(maxsum))

Lab exercises 2 Must be uploaded just after the end of your lab in Week 3 This lab involves developing some divide and conquer algorithms, to solve the maximum segment sum problerm Suppose you are given a list of integers (so some might be negative). The maximum segment sum of the list is the contiguous sublist whose sum is the largest. (Note that there's an ambiguity if there are Os in the list; these are not usually counted in the maximum segment, so we're actually looking for the shortest sequence with the largest sum For example if the list is [2 45 -7 3-614], then the maximum segment sum is 11 and the corresponding segment is [2 4 5]. Notice that negative numbers don't necessary act as stoppers to maximum segments if the sums orn both sides are large There's an obvious O(n 2) algorithm: check the segment sum between every possible start and end position. But the goal is to develop a divide and conquer algorithm As usual, we will divide the list in half recursively; and the base case will be the segment sum of whatever short sequence you choose to stop at. But the key insight is that, if every recursive call returns information about the maximum segment sum it contains and the maximum sums that end at its right and left ends, then these results from the two children can be assembled into the same information to pass upwards. At the top level of the recursion, the contained maximum segment sum is the desired answer. (This should remind you of the maximum path in an unrooted tree problem, but in this case each recursive call can't tell if it's a left or a right child of its parent and so has to keep track of the segments that end at both left and right.) 1. Build an implementation of mss using this strategy. So that you can't just copy one of the many thousands of implementations from the Web, let's solve this specialised version: given a list of integers whose length is n compute the maximum segment sum and the elements of the maximum segment between given positions left

Explanation / Answer

Python3:

# The code is same except the return value. We are returning an array instead of a single value. array will contain maximum sum and the let and right index of
# segment. and then we will compare all the segments and return the segment containing highest value and its left and right value.

import math
def midmax(alist,low,high):
    r,l,s1,s2=0,0,0,0
    mid=(low+high)//2
    li,ri=mid,mid
    for i in range(mid-1,low-1,-1):
        s1+=alist[i]
        if(s1>l):
            l=s1
            li=i
    for i in range(mid+1,high+1):
        s2+=alist[i]
        if(s2>r):
            r=s2
            ri=i
    var=l+r+alist[mid]
    if(var>l and var>r):
        return [var,li,ri]
    elif(l>var and l>r):
        return [l,low,mid-1]
    else:
        return [r,mid+1,high]

def segmentMax(alist,l,h):
    if(l>h):
        return [-math.inf,l,h]
    else:
        mid=(h+l)//2
        seg1=segmentMax(alist,l,mid-1)
        seg2=segmentMax(alist,mid+1,h)
        seg3=midmax(alist,l,h)
      
        if(seg1[0]>seg2[0] and seg1[0]>seg3[0]):
            return seg1
        elif(seg2[0]>seg1[0] and seg2[0]>seg3[0]):
            return seg2
        else:
            return seg3

alist=[2,4,5,-7,3,-6,1,4]
n=len(alist)
seg=segmentMax(alist,0,n-1)
print("Segment from index",seg[1],"to",seg[2],"has maximum sum equal to",seg[0])

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.