Algocademy Logo

Course Outline

Maximum Sum Subarray in O(n^2) Time Complexity using JavaScript


Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.

Example:

Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

Note:

Your algorithm should run in O(n^2) time and use O(1) extra space.


Understanding the Problem

The core challenge of this problem is to find the subarray with the maximum sum in an array that contains both positive and negative integers. This problem is significant in various fields such as finance (to find the best time to buy and sell stocks) and computer science (for optimization problems).

Potential pitfalls include misunderstanding the definition of a subarray (which must be contiguous) and not considering negative numbers correctly.

Approach

To solve this problem, we can start with a naive approach and then move to more optimized solutions.

Naive Approach

The naive approach involves checking all possible subarrays and calculating their sums. This can be done using two nested loops:

let maxSum = nums[0];
for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
        let sum = 0;
        for (let k = i; k <= j; k++) {
            sum += nums[k];
        }
        maxSum = Math.max(maxSum, sum);
    }
}
return maxSum;

This approach has a time complexity of O(n^3) and is not optimal.

Optimized Approach

We can optimize the above approach by calculating the sum of subarrays in O(1) time using a running sum:

let maxSum = nums[0];
for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
        sum += nums[j];
        maxSum = Math.max(maxSum, sum);
    }
}
return maxSum;

This approach reduces the time complexity to O(n^2).

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

  1. Initialize maxSum with the first element of the array.
  2. Use a nested loop to iterate through all possible subarrays.
  3. In the inner loop, maintain a running sum of the current subarray.
  4. Update maxSum if the current subarray sum is greater than maxSum.
  5. Return maxSum after all iterations.

Code Implementation

/**
 * Function to find the maximum sum of a continuous subarray
 * @param {number[]} nums - The input array
 * @return {number} - The maximum sum of the subarray
 */
function maxSubArray(nums) {
    // Initialize maxSum with the first element of the array
    let maxSum = nums[0];
    
    // Iterate through each possible starting point of the subarray
    for (let i = 0; i < nums.length; i++) {
        // Initialize the sum of the current subarray
        let sum = 0;
        
        // Iterate through each possible ending point of the subarray
        for (let j = i; j < nums.length; j++) {
            // Add the current element to the sum
            sum += nums[j];
            
            // Update maxSum if the current sum is greater
            maxSum = Math.max(maxSum, sum);
        }
    }
    
    // Return the maximum sum found
    return maxSum;
}

// Example usage
const nums = [-2, -5, 6, -2, -3, 1, 5, -6];
console.log(maxSubArray(nums)); // Output: 7

Complexity Analysis

The time complexity of the optimized approach is O(n^2) because of the two nested loops. The space complexity is O(1) as we are using only a few extra variables.

Edge Cases

Consider the following edge cases:

  • All negative numbers: The algorithm should return the least negative number.
  • Single element array: The algorithm should return that element.
  • Array with all zeros: The algorithm should return zero.

Example edge cases:

console.log(maxSubArray([-1, -2, -3])); // Output: -1
console.log(maxSubArray([0])); // Output: 0
console.log(maxSubArray([0, 0, 0])); // Output: 0

Testing

To test the solution comprehensively, consider using a variety of test cases, including simple, complex, and edge cases. You can use testing frameworks like Jest or Mocha for automated testing.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

  • Break down the problem into smaller parts.
  • Start with a naive solution and then optimize.
  • Think about edge cases and how to handle them.
  • Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to find the maximum sum subarray in an array containing both positive and negative integers. We started with a naive approach and then optimized it to achieve O(n^2) time complexity. Understanding and solving such problems is crucial for improving algorithmic thinking and problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: