Start learning free

LESSON 227 OF 410 · FREE CODING INTERVIEW QUESTIONS

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

Practice O(n2) Read the full explanation

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.




Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the subarrays of nums. How can we try out each subarray?

A subarray is defined by its left endpoint, let's name it index i and its right point, let's name it index j. We should go through each pair of indices (i, j) such that 0 <= i <= j < n, where n is the length of nums. How can we achieve this?

Using two nested for loops! The first loop will try out each possible i between 0 and n - 1. The second loop will be written inside the first one and will try out each possible j between i and n - 1. 
for each i : 0 to n - 1:
		for each j : i to n - 1:
We will use a variable maxSum to store the greatest sum found so far and for each pair (i, j), update maxSum with sum(nums[i...j]) if it's the case: 
maxSum = nums[0]
for each i : 0 to n - 1:
	for each j : i to n - 1:
		maxSum = max(maxSum, sum(nums[i...j]))
return maxSum
All we have to do now is find a way of getting sum(nums[i...j]) in O(1) time. How can we do this?

One way is using Partial Sums. But that implies using an extra array, which takes O(n) extra space. There is a better way. We can use a variable sum to store the sum of the current subarray sum(nums[i...j]). 
maxSum = nums[0]
for each i : 0 to n - 1:
	for each j : i to n - 1:
		maxSum = max(maxSum, sum)
return maxSum
How should we update this variable throught the algorithm to make sure that it always stores the correct sum?

Each time we increment j in the second loop, we should add nums[j] to sum. Also, each time we increment i in the first loop, we start with a new empty subarray so we should reset sum to 0: 
maxSum = nums[0]
for each i : 0 to n - 1:
	sum = 0
	for each j : i to n - 1:
		sum += nums[j]
		maxSum = max(maxSum, sum)
return maxSum

STEP 1 OF 7
    Ctrl + Enter to check

    JAVA · FREE CODING INTERVIEW QUESTIONS

    Maximum Sum Subarray in Java, explained

    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:

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

    However, this approach has a time complexity of O(n^3), which is not efficient for large arrays.

    Optimized Approach

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

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

    This reduces the time complexity to O(n^2) while maintaining O(1) space complexity.

    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

    public class MaximumSumSubarray {
    public static int maxSubArray(int[] nums) {
        // Initialize maxSum with the first element of the array
        int maxSum = nums[0];
        
        // Iterate through each possible starting point of the subarray
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            // Iterate through each possible ending point of the subarray
            for (int j = i; j < nums.length; j++) {
                // Add the current element to the running sum
                sum += nums[j];
                // Update maxSum if the current subarray sum is greater
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2, -5, 6, -2, -3, 1, 5, -6};
        System.out.println("Maximum Sum Subarray: " + 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 maximum single element.
    • Single element array: The algorithm should return that element.
    • All positive numbers: The algorithm should return the sum of the entire array.

    Examples:

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

Input: nums = [5]
Output: 5

Input: nums = [1, 2, 3, 4]
Output: 10

    Testing

    To test the solution comprehensively, consider a variety of test cases:

    • Simple cases with small arrays.
    • Edge cases with all negative or all positive numbers.
    • Large arrays to test performance.

    Use a testing framework like JUnit to automate the testing process.

    Thinking and Problem-Solving Tips

    When approaching such problems:

    • Understand the problem requirements and constraints.
    • Start with a brute force solution to get a basic understanding.
    • Look for patterns and ways to optimize the solution.
    • Practice similar problems to improve problem-solving skills.

    Conclusion

    In this blog post, we discussed the problem of finding the maximum sum subarray in an array containing both positive and negative integers. We explored a naive approach and an optimized approach, provided a detailed algorithm, and implemented the solution in Java. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.

    Additional Resources

    For further reading and practice, consider the following resources:


    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free