How to return the maximum subarray using brute force?

userv6Cl1 0
Viewed 49

This is my code for returning the maximum subarray SUM using brute force, but would it be possible to return the actual subarray instead?

public static int[] findMaximumSubArray(int[] nums){
    int curMax = nums[0];
    for(int i = 0; i < nums.length; i++) {
        int sum = nums[i];
        curMax = Math.max(sum,  curMax);
        
        for(int j = i + 1; j < nums.length; j++) {
            sum += nums[j];
            curMax = Math.max(sum,  curMax);
        }
    }
    return curMac;
brute-force java arrays
1 Answers

In addition to keeping track of the current maximum sum, you should also keep track of the current maximum sub array. You can easily do this by just keeping track of its start and end positions.

// assume non-empty array
int maxStart = 0;
int maxEnd = 0;
int curMax = nums[0];

Rather than using Math.max, expand that into an if (sum > curMax) check so that you can also set maxStart and maxEnd in there:

In the outer loop, since it finds the start position, replace Math.max with:

if (sum > curMax) {
    curMax = sum;
    maxStart = i;
    maxEnd = i;
}

In the inner loop, since it finds both the start position and the end position, replace the Math.max call with:

if (sum > curMax) {
    curMax = sum;
    maxStart = i;
    maxEnd = j;
}

Finally, return a copy of the specified range of the array:

return Arrays.copyOfRange(nums, maxStart, maxEnd + 1);

Note that the subarray with the maximum sum is not unique. For example, the array { 0, 1, 0 } has 4 subarrays that all add up to 1. This algorithm finds the shortest among the ones that starts the earliest.

Full code looks like this:

public static int[] findMaximumSubArray(int[] nums) {
    int maxStart = 0;
    int maxEnd = 0;
    int curMax = nums[0];
    for (int i = 0; i < nums.length; i++) {
        int sum = nums[i];
        if (sum > curMax) {
            curMax = sum;
            maxStart = i;
            maxEnd = i;
        }

        for (int j = i + 1; j < nums.length; j++) {
            sum += nums[j];
            if (sum > curMax) {
                curMax = sum;
                maxStart = i;
                maxEnd = j;
            }
        }
    }
    return Arrays.copyOfRange(nums, maxStart, maxEnd + 1);
}
Sweeper0
Related