Question

Create a greedy solution to the MaxSumSubArray problem, describe it and it's runtime, and prove it's optimal

Code it in python

Answer 1

please check out the photos for better understanding.... And please do a comment for any doubt, thank you...

The algorithm for the MaxSumSubArray is known as Kadane's Algorithm which follows Greedy and Dynamic approach to find the optimal solution... It's a standard Algorithm...

algorithm...(picture)

At first,Max,Max_all is assigned to 0

then for all element in the array, we have to add the current elements with the Max_all and then store it again in Max_all until Max_all becomes <0 i.e. negetive

tnen compare the Max with Max_all and find if Max < Max_all. if so,then assign Max=Max_all

This is the approach...

Runtime:

the for loop is running from 0 to n-1 where n is the size of the array...

So, the Running Complexity of the algorithm is O(n)

optimal?

the algorithm is optimal except one condition... if all the elements in the array are negative, the algorithm gives wrong answer...

There is a solution for that...at first we have to check if all the elements are negative or nor, if so, then max sum sub array will be the largest element of the array...

now this will be the optimal answer...

code: (optimal code)

def MaxSumSubArray(arr,n) :
        Max=max(arr)   #finding the maximum element in the array
        if Max<0:   
                return Max    #if maximum is negative, then all the elements in the array is negative
        Max=Max_all=0    #else assigning Max=0 and Max_all=0
        for i in range(0,n) :    #for all element in arr
                Max_all+=arr[i]
                if Max < Max_all :
                        Max = Max_all
                if Max_all < 0 :   #if Max_all is negative
                        Max_all = 0
        return Max;   #returning max
print("Input the array Elements :")
arr = [int (x) for x in input().split()]   #array input separated by space
n=len(arr)   #calculating the length of the array
print("Maximum Sum of SubArray is : ", MaxSumSubArray(arr,n))  #calling function

#end of program

output...

screen sort of code: