Java Program to Find Maximum Subarray Sum

Use Kadane's algorithm in Java by iterating through the array, updating current and maximum sums with currentSum = Math.max(arr[i], currentSum + arr[i]) and maxSum = Math.max(maxSum, currentSum) to find the maximum subarray sum.

Examples

Input[1, -2, 3, 4, -1, 2, 1, -5, 4]

Output9

Input[-3, -2, -1, -4]

Output-1

Input[5, 4, -1, 7, 8]

Output23

How to Think About It

To find the maximum sum of a continuous subarray, move through the array while keeping track of the current sum of the subarray. If adding the current element makes the sum smaller than the element itself, start a new subarray from the current element. Keep updating the maximum sum found so far.

Algorithm

1

Initialize two variables: currentSum and maxSum with the first element of the array.

2

Iterate through the array starting from the second element.

3

For each element, update currentSum to be the maximum of the element itself or currentSum plus the element.

4

Update maxSum if currentSum is greater than maxSum.

5

After the loop ends, return maxSum as the maximum subarray sum.

Code

java

public class MaxSubarraySum {
    public static int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
    public static void main(String[] args) {
        int[] arr = {1, -2, 3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(arr));
    }
}

Output

9

Dry Run

Let's trace the array [1, -2, 3, 4, -1, 2, 1, -5, 4] through the code

1

Initialize

currentSum = 1, maxSum = 1

2

Index 1 (-2)

currentSum = max(-2, 1 + (-2)) = max(-2, -1) = -1; maxSum = max(1, -1) = 1

3

Index 2 (3)

currentSum = max(3, -1 + 3) = max(3, 2) = 3; maxSum = max(1, 3) = 3

4

Index 3 (4)

currentSum = max(4, 3 + 4) = max(4, 7) = 7; maxSum = max(3, 7) = 7

5

Index 4 (-1)

currentSum = max(-1, 7 + (-1)) = max(-1, 6) = 6; maxSum = max(7, 6) = 7

6

Index 5 (2)

currentSum = max(2, 6 + 2) = max(2, 8) = 8; maxSum = max(7, 8) = 8

7

Index 6 (1)

currentSum = max(1, 8 + 1) = max(1, 9) = 9; maxSum = max(8, 9) = 9

8

Index 7 (-5)

currentSum = max(-5, 9 + (-5)) = max(-5, 4) = 4; maxSum = max(9, 4) = 9

9

Index 8 (4)

currentSum = max(4, 4 + 4) = max(4, 8) = 8; maxSum = max(9, 8) = 9

Index	Element	currentSum	maxSum
0	1	1	1
1	-2	-1	1
2	3	3	3
3	4	7	7
4	-1	6	7
5	2	8	8
6	1	9	9
7	-5	4	9
8	4	8	9

Why This Works

Step 1: Track current sum

We keep a running sum of the current subarray using currentSum. If adding the next element makes the sum smaller than the element alone, we start fresh from that element.

Step 2: Update maximum sum

At each step, we compare currentSum with maxSum and update maxSum if currentSum is larger, ensuring we remember the best sum found.

Step 3: Return result

After checking all elements, maxSum holds the largest sum of any continuous subarray, which we return.

Alternative Approaches

Brute Force

java

public static int maxSubArrayBruteForce(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int currentSum = 0;
        for (int j = i; j < nums.length; j++) {
            currentSum += nums[j];
            if (currentSum > maxSum) maxSum = currentSum;
        }
    }
    return maxSum;
}

Checks all subarrays but is slow with O(n^2) time, simple but inefficient for large arrays.

Divide and Conquer

java

public static int maxSubArrayDivideConquer(int[] nums, int left, int right) {
    if (left == right) return nums[left];
    int mid = (left + right) / 2;
    int leftMax = maxSubArrayDivideConquer(nums, left, mid);
    int rightMax = maxSubArrayDivideConquer(nums, mid + 1, right);
    int crossMax = maxCrossingSum(nums, left, mid, right);
    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

private static int maxCrossingSum(int[] nums, int left, int mid, int right) {
    int sum = 0, leftSum = Integer.MIN_VALUE;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        if (sum > leftSum) leftSum = sum;
    }
    sum = 0;
    int rightSum = Integer.MIN_VALUE;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        if (sum > rightSum) rightSum = sum;
    }
    return leftSum + rightSum;
}

Uses recursion to split array, faster than brute force but more complex and uses extra stack space.

Complexity: O(n) time, O(1) space

Time Complexity

Kadane's algorithm scans the array once, updating sums in constant time per element, resulting in O(n) time.

Space Complexity

It uses only a few variables for sums, so space complexity is O(1), no extra arrays needed.

Which Approach is Fastest?

Kadane's algorithm is fastest and simplest for this problem compared to brute force O(n^2) or divide and conquer O(n log n).

Approach	Time	Space	Best For
Kadane's Algorithm	O(n)	O(1)	Large arrays, efficient solution
Brute Force	O(n^2)	O(1)	Small arrays, simple implementation
Divide and Conquer	O(n log n)	O(log n)	When recursion or parallelism is preferred