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

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

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

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

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

Repovive

Maximum Subarray - D&C - Divide and Conquer | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Maximum Subarray - D&C

Kadane's alternative using divide and conquer.

Problem: Find contiguous subarray with maximum sum.

D&C: Split in half. Max subarray is in left half, right half, or crossing middle.

Crossing: Extend left from mid, extend right from mid+1, sum both max extensions.

function maxCrossing(arr, left, mid, right):
    leftMax = extend left from mid
    rightMax = extend right from mid+1
    return leftMax + rightMax

Time: $O(n \log n)$ . Kadane's is $O(n)$ , but D&C illustrates the technique.