Given an array of integers, the task is to find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray with the largest sum is [4, -1, 2, 1], and the sum is 6.

Approaches to Solve:

• Brute Force Approach: The brute force approach involves generating all possible subarrays and calculating their sums. The maximum sum among these sums is the desired result. However, this approach has a time complexity of O(n^3), making it inefficient for large arrays.

• Divide and Conquer: The Divide and Conquer approach splits the array into halves recursively until it becomes a single element. Then, it combines the results from the left and right halves to find the maximum subarray crossing the midpoint. This approach has a time complexity of O(n log n).

const mainArray = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSubArray = (myArray) => {
    let maxSum = myArray[0];
    for (let i = 0; i < myArray.length; i++) {
        let tempSum = myArray[i]
        for (let j = i+1; j < myArray.length; j++) {
            tempSum += myArray[j]
            if (tempSum > maxSum) {
                maxSum = tempSum;
            }
        }
    }

    return {maxArray,maxSum};
}

console.log(maxSubArray(mainArray));

• Kadane's Algorithm: Kadane's Algorithm is the most efficient solution to the Maximum Subarray problem. It iterates through the array, keeping track of the maximum subarray sum ending at each position. This algorithm has a time complexity of O(n) and is widely used due to its simplicity and efficiency.

const mainArray = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSubArray = (myArray) => {
    let maxSum = myArray[0]
    let currentSum = myArray[0]
    for (let i = 0 ; i < myArray.length ; i++ ){
        currentSum = Math.max(myArray[i], currentSum + myArray[i])
        maxSum = Math.max(currentSum, maxSum)
    }

    return maxSum;
}

console.log(maxSubArray(mainArray));

Conclusion:

The Maximum Subarray Algorithm is a fundamental problem with various real-world applications. Understanding its intricacies and efficient solutions like Kadane's Algorithm is crucial for algorithmic problem-solving and data analysis tasks. By leveraging this algorithm, developers can optimize their solutions and tackle complex problems effectively.