Find Maximum Subarray Divide and Conquer in DSA C - Build from Scratch

Find Maximum Subarray using Divide and Conquer

📖 Scenario: You are analyzing daily temperature changes to find the longest period of increasing temperature. This can be represented as finding the maximum sum of a contiguous subarray in an array of integers.

🎯 Goal: Build a program in C that uses the divide and conquer method to find the maximum sum of a contiguous subarray in a given integer array.

📋 What You'll Learn

Create an integer array called arr with the exact values: {2, -4, 3, -1, 5, -6, 1, 4, -2, 3}

Create two integer variables called low and high to represent the start and end indices of the array

Write a function called maxCrossingSum that finds the maximum subarray sum crossing the midpoint

Write a recursive function called maxSubArraySum that uses divide and conquer to find the maximum subarray sum

Print the maximum subarray sum found by calling maxSubArraySum(arr, low, high)

💡 Why This Matters

🌍 Real World

Finding maximum subarrays is useful in financial analysis to find the best time to buy and sell stocks for maximum profit.

💼 Career

Understanding divide and conquer algorithms and recursion is essential for software engineering roles that require problem-solving and optimization skills.

1

Create the integer array

Create an integer array called arr with these exact values: {2, -4, 3, -1, 5, -6, 1, 4, -2, 3}

DSA C

# Create the integer array 'arr' with the given values
// Your code here

Hint

Use int arr[] = {2, -4, 3, -1, 5, -6, 1, 4, -2, 3}; to create the array.

2

Set the low and high indices

Create two integer variables called low and high. Set low to 0 and high to 9 (the last index of arr).

DSA C

#include 

int arr[] = {2, -4, 3, -1, 5, -6, 1, 4, -2, 3};

// Create low and high indices
// Your code here

Hint

Set low to 0 and high to 9 because the array has 10 elements indexed 0 to 9.

3

Write the divide and conquer functions

Write the function maxCrossingSum that takes arr, low, mid, and high and returns the maximum sum of a subarray crossing mid. Then write the recursive function maxSubArraySum that takes arr, low, and high and returns the maximum subarray sum using divide and conquer.

DSA C

#include 

int arr[] = {2, -4, 3, -1, 5, -6, 1, 4, -2, 3};

int low = 0;
int high = 9;

// Write maxCrossingSum function
// Write maxSubArraySum function
// Your code here

Hint

Use two loops in maxCrossingSum to find max sums on left and right of mid. Use recursion in maxSubArraySum to divide the array.

4

Print the maximum subarray sum

Write a main function that calls maxSubArraySum(arr, low, high) and prints the result with printf.

DSA C

#include 

int arr[] = {2, -4, 3, -1, 5, -6, 1, 4, -2, 3};

int low = 0;
int high = 9;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int maxCrossingSum(int arr[], int low, int mid, int high) {
    int sum = 0;
    int left_sum = -2147483648; // very small number
    for (int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > left_sum)
            left_sum = sum;
    }

    sum = 0;
    int right_sum = -2147483648;
    for (int i = mid + 1; i  right_sum)
            right_sum = sum;
    }

    return left_sum + right_sum;
}

int maxSubArraySum(int arr[], int low, int high) {
    if (low == high)
        return arr[low];

    int mid = (low + high) / 2;

    int left_max = maxSubArraySum(arr, low, mid);
    int right_max = maxSubArraySum(arr, mid + 1, high);
    int cross_max = maxCrossingSum(arr, low, mid, high);

    return max(max(left_max, right_max), cross_max);
}

// Write main function to print the maximum subarray sum
// Your code here

Hint

Call maxSubArraySum(arr, low, high) and print the result using printf.