#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/maximum-subarray-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/maximum-subarray-implementation

Repovive

Maximum Subarray - Implementation - Divide and Conquer | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Maximum Subarray - Implementation

Here is the implementation:

function maxSubArray(nums):
    return divideConquer(nums, 0, nums.length - 1)

function divideConquer(nums, left, right):
    if left == right:
        return nums[left]

    mid = (left + right) / 2
    leftMax = divideConquer(nums, left, mid)
    rightMax = divideConquer(nums, mid + 1, right)
    crossMax = maxCrossing(nums, left, mid, right)

    return max(leftMax, rightMax, crossMax)

function maxCrossing(nums, left, mid, right):
    leftSum = -infinity, sum = 0
    for i from mid down to left:
        sum += nums[i]
        leftSum = max(leftSum, sum)

    rightSum = -infinity, sum = 0
    for i from mid + 1 to right:
        sum += nums[i]
        rightSum = max(rightSum, sum)

    return leftSum + rightSum