Maximum Subarray Sum in Java

When working with arrays, one common problem is finding the maximum sum of a subarray. A subarray is simply a continuous part of the array. The goal is to pick a portion of the array such that the sum of its elements is as large as possible.

Understanding the Problem

Given an integer array, which may contain both positive and negative numbers, we need to find the maximum possible sum of any continuous subarray.

For example
Array: [−2, 1, −3, 4, −1, 2, 1, −5, 4]
Output: 6
Explanation: The subarray [4, −1, 2, 1] gives the maximum sum.

Simple Idea

The best way to solve this problem is using a method called Kadane’s Algorithm. The idea is simple:

At each step, decide whether to:

1. Continue the current subarray
2. Start a new subarray from the current element

We keep track of:

• Current sum of subarray
• Maximum sum found so far

Algorithm Steps

1. Start with two variables:

• currentSum = first element
• maxSum = first element

1. Traverse the array from the second element

2. For each element:

• Add it to currentSum
• If the current element alone is greater than currentSum, start new subarray
• Update maxSum if currentSum is greater

1. At the end, maxSum will have the answer

Java Code

public class MaximumSubarray {
public static int maxSubArray(int[] arr) {
int currentSum = arr[0];
int maxSum = arr[0];

    for (int i = 1; i < arr.length; i++) {
        currentSum = Math.max(arr[i], currentSum + arr[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

public static void main(String[] args) {
    int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int result = maxSubArray(arr);
    System.out.println("Maximum Subarray Sum: " + result);
}

}

Time and Space Complexity

Time Complexity: O(n) because we traverse the array only once
Space Complexity: O(1) because no extra space is used

Why This Works

Instead of checking all possible subarrays, which would take a lot of time, this method keeps updating the best sum while moving forward. It avoids unnecessary calculations and gives the answer efficiently.

Conclusion

Finding the maximum subarray sum is an important problem in programming. Using Kadane’s Algorithm makes it simple and efficient. It is widely used because of its speed and simplicity. Understanding this concept will help in solving many similar problems.