Maximum Subarray

class Solution {
private:
    vector<int> elements;

public:
    int maximumSubArray(vector<int>& nums) {
        elements = nums;
        return calculateSubarray(0, elements.size() - 1);
    }
    int calculateSubarray(int left, int right) {
        if (left > right) {
            return INT_MIN;
        }
        int midpoint = (left + right) / 2;
        int sum = 0;
        int maxLeftSum = 0;
        int maxRightSum = 0;
        for (int i = midpoint - 1; i >= left; i--) {
            sum += elements[i];
            maxLeftSum = max(maxLeftSum, sum);
        }
        sum = 0;
        for (int i = midpoint + 1; i <= right; i++) {
            sum += elements[i];
            maxRightSum = max(maxRightSum, sum);
        }
        int maxCrossingSum = elements[midpoint] + maxLeftSum + maxRightSum;
        int maxLeftHalf = calculateSubarray(left, midpoint - 1);
        int maxRightHalf = calculateSubarray(midpoint + 1, right);
        return max(maxCrossingSum, max(maxLeftHalf, maxRightHalf));
    }
};

The solution provided is a C++ implementation for solving the Maximum Subarray problem, which aims to find the contiguous subarray (containing at least one number) which has the largest sum among all subarrays of a given array of integers.

• The Solution class is designed with two main functions:

  • maximumSubArray is the public interface function which initializes the elements vector with the input array and calls the recursive calculateSubarray function.
  • calculateSubarray is a private recursive function that computes the maximum sum of subarrays divided by a divide and conquer approach.

• The divide and conquer strategy works by:

  • Dividing the array into left, right, and middle parts.
  • Recursively finding the maximum subarray sums for the left and the right halves.
  • Finding the maximum subarray sum that crosses the middle element by adding the maximum sums from both sides of the middle point.

• The recursion ends when the base case is reached, where the left index surpasses the right index, at which point the function returns a minimal integer value as no sum is possible.

• This approach ensures all possible subarrays are considered. It uses a combination of linear iterations for crossing sums and recursive calls for left and right half sums, effectively navigating through the entire array to ensure that the maximum possible sum is computed.

• The strategy efficiently handles array indexing and element access efficiently to minimize overheads and achieve optimal performance. The recursive depth and multiple indices are well managed to avoid confusion and ensure a systematic and clear subdivision of the problem at each step.

• By comparing maximum sums across different sections of the array and combining them effectively, the solution guarantees that the highest subarray sum is obtained, handling even negative numbers correctly through comparison with zero and the use of INT_MIN to represent untenably low sums.

class Solution {
    private int[] dataArray;

    public int maxSequence(int[] data) {
        dataArray = data;

        return calculateMaxSubsequence(0, dataArray.length - 1);
    }

    private int calculateMaxSubsequence(int start, int end) {
        if (start > end) {
            return Integer.MIN_VALUE;
        }

        int middle = (start + end) / 2;
        int sum = 0;
        int maxLeft = 0;
        int maxRight = 0;

        for (int i = middle - 1; i >= start; i--) {
            sum += dataArray[i];
            maxLeft = Math.max(maxLeft, sum);
        }

        sum = 0;
        for (int i = middle + 1; i <= end; i++) {
            sum += dataArray[i];
            maxRight = Math.max(maxRight, sum);
        }

        int maxCrossing = dataArray[middle] + maxLeft + maxRight;

        int bestLeft = calculateMaxSubsequence(start, middle - 1);
        int bestRight = calculateMaxSubsequence(middle + 1, end);

        return Math.max(maxCrossing, Math.max(bestLeft, bestRight));
    }
}

The provided Java solution is designed to find the maximum sum of any contiguous subarray within a given integer array. This problem is commonly solved using the "divide and conquer" approach, as illustrated in this implementation.

The solution consists of the Solution class which contains two primary functions:

• maxSequence(int[] data): This function initializes the data array and invokes the recursive function calculateMaxSubsequence on the entire array.
• calculateMaxSubsequence(int start, int end): This function recursively divides the array into halves to find the maximum subarray sum. It calculates the maximum sums of the left and right subarrays as well as the sum of subarrays crossing the middle element, then returns the maximum of these three sums.

The recursive function uses the following steps to compute the solution:

1. Determine the base case where if the start index exceeds the end index, return the smallest possible integer value.
2. Calculate the middle index of the current segment of the array.
3. Compute maximum sums for the left part ending at middle-1 and the right part starting at middle+1.
4. Compute the maximum sum crossing the middle by adding maximum left and right sums to the middle element's value.
5. Recursively find the maximum subarray sums for the left and right halves of the array.
6. Return the maximum value among the left, right, and crossing subarrays.

This algorithm is efficient in solving the maximum subarray problem by breaking it down into smaller subproblems, solving each independently, and combining their solutions. The recursive division of the array ensures that each possible subarray is considered, while the use of maximum calculations consolidates these into the overall solution.

int maxArraySum(int* arr, int size) {
    return bestSubArraySum(arr, 0, size - 1);
}
int bestSubArraySum(int* arr, int start, int end) {
    if (start > end) {
        return INT_MIN;
    }
    int middle = (start + end) / 2;
    int sum = 0;
    int maxLeftSum = 0;
    int maxRightSum = 0;
    for (int i = middle - 1; i >= start; i--) {
        sum += arr[i];
        maxLeftSum = fmax(maxLeftSum, sum);
    }
    sum = 0;
    for (int i = middle + 1; i <= end; i++) {
        sum += arr[i];
        maxRightSum = fmax(maxRightSum, sum);
    }
    int maxCrossingSum = arr[middle] + maxLeftSum + maxRightSum;
    int maxLeftPartSum = bestSubArraySum(arr, start, middle - 1);
    int maxRightPartSum = bestSubArraySum(arr, middle + 1, end);
    return fmax(maxCrossingSum, fmax(maxLeftPartSum, maxRightPartSum));
}

The provided C code implements a solution to the maximum subarray problem, which is to find the contiguous subarray with the maximum sum within a given array. This implementation uses a divide-and-conquer approach inspired by the classic algorithm.

Here's a breakdown of the solution technique:

1. Two primary functions are defined, maxArraySum and bestSubArraySum.
2. The maxArraySum function initiates the recursion. It passes the entire array and its boundaries (from 0 to size - 1) to the bestSubArraySum function.
3. The bestSubArraySum function recursively divides the given part of the array into halves until the subarrays contain only one element or no elements.
4. For each segment, a middle index is calculated, and from there, the function explores left to the boundary on the left and right to the boundary on the right to find the max possible sum contiguous subarrays in both directions.
5. It calculates sums extending from the middle index outwards to both left and right bounds (maxLeftSum and maxRightSum respectively). This handles the case where the max subarray spans across the middle.
6. The function uses a supplementary loop to compute the sum when crossing from left to right, through the middle.
7. Lastly, the main recursive function compares three values to determine the largest subarray sum for the combined segments:
   • Subarray sum that lies completely in the left half (maxLeftPartSum)
   • Subarray sum that lies completely in the right half (maxRightPartSum)
   • Sum across the left and right subarrays through the middle element (maxCrossingSum)

The fmax function from the math.h library supports finding the maximum of the competing sums effectively.

This divide-and-conquer approach essentially optimizes the search for the maximum subarray sum by breaking down the problem and combining solutions, which is more manageable and efficient in practice than simpler, brute-force methods.

var maxSubarraySum = function (arr) {
    return calculateSubarray(arr, 0, arr.length - 1);
};
var calculateSubarray = function (arr, lft, rgt) {
    if (lft > rgt) {
        return -Infinity;
    }
    let middle = Math.floor((lft + rgt) / 2);
    let currentSum = 0;
    let maxLeftSubSum = 0;
    let maxRightSubSum = 0;
    for (let j = middle - 1; j >= lft; j--) {
        currentSum += arr[j];
        maxLeftSubSum = Math.max(maxLeftSubSum, currentSum);
    }
    currentSum = 0;
    for (let j = middle + 1; j <= rgt; j++) {
        currentSum += arr[j];
        maxRightSubSum = Math.max(maxRightSubSum, currentSum);
    }
    let maxCrossSum = arr[middle] + maxLeftSubSum + maxRightSubSum;
    let maxSubSumLeft = calculateSubarray(arr, lft, middle - 1);
    let maxSubSumRight = calculateSubarray(arr, middle + 1, rgt);
    return Math.max(maxCrossSum, Math.max(maxSubSumLeft, maxSubSumRight));
};

This summary discusses a solution for finding the maximum subarray sum using JavaScript. The provided implementation uses a divide and conquer approach, similar to the one used in the merge sort algorithm. It calculates the maximum sum of a subarray in an array of integers.

• The maxSubarraySum function initiates the process and calls calculateSubarray, passing the entire array and its boundaries as parameters.

• The calculateSubarray function finds the maximum subarray sum recursively:

  • It splits the array into two halves around a middle index.
  • The function considers three cases for the maximum subarray sum:
    • Maximum subarray sum in the left half.
    • Maximum subarray sum in the right half.
    • Maximum subarray sum that crosses the middle element combining elements from both halves.
  • For the crossing sum, the algorithm calculates the maximum sums possible from the middle to both ends of the current subarray segment.
  • It uses these calculations, including contributions from both halves of the array, to determine the maximum sum crossing the middle.

• The recursive division continues until the base case where the sub-array has fewer elements, and the solution to each smaller problem combines to solve the larger problem.

• It uses Math.max to determine the overall maximum sum among the left, right, and crossing sums.

• This recursive division allows the algorithm to efficiently tackle the problem, with each level of recursion breaking down the problem into smaller and easier-to-solve segments.

The solution flexibly handles varying input sizes and efficiently calculates required values, demonstrating the power of recursive algorithms in solving complex problems.

class Solution:
    def findMaximumSubArray(self, arr: List[int]) -> int:
        def calculateMaxSubArray(seq, start, end):
            if start > end:
                return float('-inf')

            center = (start + end) // 2
            sum_current = max_left = max_right = 0

            for index in range(center - 1, start - 1, -1):
                sum_current += seq[index]
                max_left = max(max_left, sum_current)

            sum_current = 0
            for index in range(center + 1, end + 1):
                sum_current += seq[index]
                max_right = max(max_right, sum_current)

            max_combined = seq[center] + max_left + max_right

            left_part_max = calculateMaxSubArray(seq, start, center - 1)
            right_part_max = calculateMaxSubArray(seq, center + 1, end)

            return max(max_combined, left_part_max, right_part_max)

        return calculateMaxSubArray(arr, 0, len(arr) - 1)

The provided Python code implements a solution to finding the maximum sum subarray using a recursive approach, specifically a divide and conquer algorithm.

• The function findMaximumSubArray is defined to work on an input list of integers.

• Inside this function, a nested helper function calculateMaxSubArray is defined, which handles the recursion and calculation of the maximum sum subarray.

• The calculateMaxSubArray function takes three parameters: seq (the list of integers), start (starting index of the subarray), and end (ending index of the subarray).

• If the start index is greater than the end index, it returns negative infinity, representing an invalid subarray.

• The function calculates the center of the sequence and initializes variables to store current sums and maximum sums for the left and right sections around the center.

• It then iterates both leftwards and rightwards from the center to find maximum subarrays that include the center element.

• The maximum combined sum including the center, left maximum, and right maximum is stored in max_combined.

• Recursively, the function finds the maximum subarrays for the left and right halves, excluding the center.

• Finally, the maximum of three potential maximum values (max_combined, the result from the left partition, and the result from the right partition) is returned.

• The top-level call initiates the process with the whole array from index 0 to len(arr) - 1.

This code effectively breaks down the problem into smaller subproblems, handles them individually, and then combines results to achieve the maximum sum subarray. Ensure input arrays are non-empty to avoid unexpected behavior due to the recursive structure.