Maximum subarray problem is the task of finding a contiguous subarray with the largest sum. For example, for the array of values [−2, 1, −3, 4, −1, 2, 1, −5, 4], the contiguous subarray with the largest sum is [4, −1, 2, 1], with sum 6.

The brute force solution would be to create two pointers, keep one pointer constant and incremement the other (inner)pointer. Calculate the sum and keep checking for maximum sum. Once the inner pointer is exhausted, increment the outer pointer and repeat the same process. Following is the pseudo code:

1
2
3
4
5
6
7
8

for(int i = 0; i < n; i++){
int sum = 0;
for(int j = i; j < n; j++){
sum += arr[j]
maxSum = max(sum, maxSum)
}
}
return maxSum;

The above solution takes O(n^{2}) time.

Kadane’s algorithm to the rescue! In a nutshell, the algorithm states that either the maximum subarray sum ending at position i+1 includes the maximum subarray sum ending at position i as a prefix or it doesn’t.

Following is the solution to the problem using Kadane’s algorithm.

1
2
3
4
5
6
7
8
9
10
11

public int maxSubArray(int[] nums) {
int finalMaxSum = nums[0];
int maxSumSoFar = nums[0];
for(int i = 1; i < nums.length; i++){
maxSumSoFar = Math.max(nums[i], nums[i] + maxSumSoFar);
finalMaxSum = Math.max(maxSumSoFar, finalMaxSum);
}
return finalMaxSum;
}

Reference: maximum subarray problem wikipedia