Select Page

## Maximum Subarray Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array `[-2,1,-3,4,-1,2,1,-5,4]`,
the contiguous subarray `[4,-1,2,1]` has the largest sum = 6.

## Reduction Transition Function

Consider the question in the following way:

• Assume max subarray ending at nums[i] is nums[k, i]
• What about max subarray ending at nums[i + 1]

There are two options:

• Add nums[i + 1] into the max subarray ending at nums[i], which is nums[k, i]
• Begin anew, max subarray ending at nums[i + 1] is nums[i + 1]

We don’t need to consider adding part of nums[k, i] with nums[i + 1]. Why? Because:

• If sum(nums[k, i]) > 0, we want to add all of it
• If sum(nums[k, i]) < 0, we don’t want to add any of the element.

Thus we have the following RTF:

localMax[i + 1] = localMax[i] > 0 ? local_max[i] + nums[i + 1] : nums[i + 1]

The following diagram illustrates whether to combine nums[i + 1] with nums[k, i] or to start anew:

Then how does these localMax enable us to find the global max subarray? The following diagram illustrates the reason:

LocalMax either extend or begin anew. Thus the array is segmented by all possible localMax, and the max of them is global max, which can be proved easily.

## Implementation

The following is the implementation:

``````public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE, subMax = 0;
for (int num : nums) {
subMax = subMax > 0 ? subMax + num: num;
max = Math.max(max, subMax);
}
return max;
}``````