Max Subarray Sum Problem: A Comprehensive Guide and Implementation

The Max Subarray Sum Problem is defined as finding the maximum sum of a contiguous subarray within an array of integers. For example, given an array: [−2, 1, −3, 4, −1, 2, 1, −5, 4], the subarray [4, −1, 2, 1] has the largest sum of 6.

Kadane's Algorithm is an efficient way to solve this problem. The algorithm works by iterating through the array while keeping track of two variables: current_max, which represents the maximum sum of the subarray ending at the current position, and global_max, which represents the overall maximum sum found so far.

The logic is as follows:

• Initialize both current_max and global_max to the first element of the array.
• Iterate through each element in the array starting from the second element:
1. Add the current element to current_max.
2. If current_max is greater than global_max, update global_max.
3. If current_max becomes negative, reset it to 0 because a negative sum would only decrease the sum of any future subarray.

def max_subarray_sum(arr):
    if not arr:
        return 0

    current_max = global_max = arr[0]

    for num in arr[1:]:
        current_max = max(num, current_max + num)
        if current_max > global_max:
            global_max = current_max

    return global_max

function maxSubarraySum(arr) {
    if (arr.length === 0) return 0;

    let currentMax = globalMax = arr[0];

    for (let i = 1; i < arr.length; i++) {
        currentMax = Math.max(arr[i], currentMax + arr[i]);
        if (currentMax > globalMax) {
            globalMax = currentMax;
        }
    }

    return globalMax;
}

func maxSubarraySum(arr []int) int {
    if len(arr) == 0 {
        return 0
    }

    currentMax := globalMax := arr[0]

    for _, num := range arr[1:] {
        currentMax = max(num, currentMax+num)
        if currentMax > globalMax {
            globalMax = currentMax
        }
    }

    return globalMax
}

fn max_subarray_sum(arr: &[i32]) -> i32 {
    if arr.is_empty() {
        0
    } else {
        let (mut current_max, mut global_max) = (arr[0], arr[0]);

        for &num in arr.iter().skip(1) {
            current_max = num.max(current_max + num);
            if current_max > global_max {
                global_max = current_max;
            }
        }

        global_max
    }
}

int maxSubarraySum(const std::vector& arr) {
    if (arr.empty()) return 0;

    int currentMax = globalMax = arr[0];

    for (size_t i = 1; i < arr.size(); ++i) {
        currentMax = std::max(arr[i], currentMax + arr[i]);
        if (currentMax > globalMax) {
            globalMax = currentMax;
        }
    }

    return globalMax;
}

Time Complexity: O(n), where n is the number of elements in the array. The algorithm iterates through the array once. Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.