Algocademy Logo

Course Outline

Video 1 of 2

Maximum Sum Subarray II in O(n) Time and O(1) Space using JavaScript

( Kadane's Algorithm )


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) time and use O(1) extra space.


Problem Definition

The problem requires finding the maximum sum of a continuous subarray within a given array of integers, which may include both positive and negative numbers.

Input:

  • An array of integers, nums.

Output:

  • An integer representing the maximum sum of a continuous subarray.

Constraints and Assumptions:

  • The algorithm should run in O(n) time complexity.
  • The algorithm should use O(1) extra space.

Example:

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

Understanding the Problem

The core challenge is to identify the subarray with the maximum sum efficiently. This problem is significant in various applications such as financial analysis, where one might need to find the period with the highest profit.

Potential pitfalls include misunderstanding the requirement for a continuous subarray and not accounting for negative numbers correctly.

Approach

To solve this problem, we can use Kadane's Algorithm, which is an efficient way to find the maximum sum subarray in linear time.

Naive Solution:

A naive approach would involve checking all possible subarrays and calculating their sums, which would result in a time complexity of O(n^2). This is not optimal for large arrays.

Optimized Solution:

Kadane's Algorithm improves upon the naive approach by maintaining a running sum of the current subarray and updating the maximum sum found so far. This approach ensures a time complexity of O(n) and space complexity of O(1).

Algorithm

Here is a step-by-step breakdown of Kadane's Algorithm:

  1. Initialize two variables: maxCurrent and maxGlobal to the first element of the array.
  2. Iterate through the array starting from the second element.
  3. For each element, update maxCurrent to be the maximum of the current element and the sum of maxCurrent and the current element.
  4. If maxCurrent is greater than maxGlobal, update maxGlobal.
  5. After iterating through the array, maxGlobal will hold the maximum sum of the subarray.

Code Implementation

/**
 * Function to find the maximum sum of a continuous subarray
 * @param {number[]} nums - The input array of integers
 * @return {number} - The maximum sum of the subarray
 */
function maxSubArray(nums) {
    // Initialize maxCurrent and maxGlobal to the first element
    let maxCurrent = nums[0];
    let maxGlobal = nums[0];

    // Iterate through the array starting from the second element
    for (let i = 1; i < nums.length; i++) {
        // Update maxCurrent to be the maximum of the current element and the sum of maxCurrent and the current element
        maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);

        // Update maxGlobal if maxCurrent is greater
        if (maxCurrent > maxGlobal) {
            maxGlobal = maxCurrent;
        }
    }

    // Return the maximum sum found
    return maxGlobal;
}

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

Complexity Analysis

The time complexity of Kadane's Algorithm is O(n) because it involves a single pass through the array. The space complexity is O(1) as it uses a constant amount of extra space.

Edge Cases

Potential edge cases include:

  • An array with all negative numbers: The algorithm should return the maximum (least negative) number.
  • An array with a single element: The algorithm should return that element.

Examples:

Input: [-1, -2, -3]
Output: -1

Input: [5]
Output: 5

Testing

To test the solution comprehensively, consider the following test cases:

  • Arrays with mixed positive and negative numbers.
  • Arrays with all positive numbers.
  • Arrays with all negative numbers.
  • Single-element arrays.

Example test cases:

console.log(maxSubArray([-2, -5, 6, -2, -3, 1, 5, -6])); // Output: 7
console.log(maxSubArray([1, 2, 3, 4, 5])); // Output: 15
console.log(maxSubArray([-1, -2, -3, -4])); // Output: -1
console.log(maxSubArray([5])); // Output: 5

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

  • Break down the problem into smaller parts and understand the requirements.
  • Think about edge cases and how your solution handles them.
  • Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the Maximum Sum Subarray problem using Kadane's Algorithm. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: