The curious case of multiple solutions. #1 maximum sub array problem

This is one of the basic questions covered in every data structures and algorithms class and book.
The problem statement is like there is an array with positive and negative numbers and we need to find the maximum sum of a sub array. I was recently asked this question in an interview and although I have seen this a million times before I couldn’t come up with multiple solutions. I could only code out one method. So I thought to write this blog post as to make it easy for me to remember the solutions as well as anyone else who might also know only one way to solve the problem.

1) divide and conquer

In this we divide the problem into smaller problems then we solve the smaller problems and combine them to find our answer. in case of divide and conquer
a. we will first find the max sum in the left sub array A[low..mid]
b. then we will find the max sum in the right sub array A[mid..high]
c. then we find the max sum in the sub array crossing the mid point A[i..mid..j]. where low <= i <= mid < j <= high.

for this method the running time will be O(NlogN)

def maxSubArray(self, nums: List[int]) -> int:

        def cross(arr,low,high,mid):
            s=0
            max_sum_left = -float('inf')
            for i in range(mid,low-1,-1):
                s+=arr[i]
                if s>max_sum_left:
                    max_sum_left=s
            s=0
            max_sum_right=-float('inf')
            for i in range(mid+1,high+1):
                s+=arr[i]
                if s>max_sum_right:
                    max_sum_right = s
            return max_sum_left + max_sum_right

        def helper(arr,low,high):

            if low==high:
                return arr[low]
            mid = (low+high)//2
            sum_left = helper(nums,low,mid)
            sum_right = helper(nums,mid+1,high)
            sum_cross = cross(arr,low,high,mid)
            return max(sum_left,sum_right,sum_cross)

        return helper(nums,0,len(nums)-1)

2) greedy method

This one says that we add the next number to my current sum and then check if my sum has increased or not. i.e suppose we have a current_sum and we encounter a new number,num then current_sum = max(current_sum+num , num) . for this method the running time will be O(n) as it takes only one linear search in the array to find the answer

def maxSubArray(self, nums: List[int]) -> int:

        curr_sol = s = nums[0]
#start with the first number in the array

        for num in nums[1:]:
            curr_sol = max(curr_sol+num,num) #check if adding a new number makes sense
            s = max(curr_sol, s)
        return s #return the max sum found in the array

3) dynamic programming

(i hate this topic in interviews)
In this we are modifying the existing array such that if we find that a previous number is positive then we add that to current number keeping track of max sum found till then. Time complexity here is also O(n) as we only need one linear search to find the answer

def maxSubArray(self, nums: List[int]) -> int:
#start with the first number
        max_sum=nums[0]

        for i in range(1,len(nums)):
#check the previous number and add to current number if its positive
            if nums[i-1]>0:
                nums[i]+=nums[i-1]
#keep track of max_sum found
            max_sum = max(nums[i],max_sum)
        return max_sum