Maximum Contiguous Subarray Sum - Java Solution

1. Introduction

In this blog post, we'll solve the "Maximum Contiguous Subarray Sum" problem, a fundamental question in the world of algorithms and data structures. This problem is often encountered in coding interviews and is key to understanding dynamic programming concepts in Java.

Problem

Given an array of integers, the objective is to find the contiguous subarray (containing at least one number) that has the largest sum and return that sum.

Example:

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

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum = 6.

2. Solution Steps

1. Initialize two integer variables: one to store the maximum subarray sum (maxSum) and the other to keep track of the current sum (currentSum).

2. Iterate through the array, adding each element to the currentSum.

3. If currentSum becomes greater than maxSum, update maxSum.

4. If currentSum becomes negative, reset it to zero.

5. Continue this process until the end of the array.

6. Return maxSum, which holds the maximum subarray sum.

3. Code Program

public class Solution {
    // Method to find the maximum contiguous subarray sum
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0]; // Initialize maxSum to the first element
        int currentSum = nums[0]; // Initialize currentSum to the first element

        // Iterate through the array starting from the second element
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]); // Update currentSum
            maxSum = Math.max(maxSum, currentSum); // Update maxSum if currentSum is larger
        }

        return maxSum; // Return the maximum subarray sum
    }

    // Main method for testing
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] inputArray = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int result = solution.maxSubArray(inputArray);
        System.out.println("Maximum Subarray Sum: " + result); // Print the result
    }
}

Output:

Maximum Subarray Sum: 6

Explanation:

Given the input array [-2,1,-3,4,-1,2,1,-5,4], the maxSubArray method finds the contiguous subarray with the largest sum. In this case, the subarray [4,-1,2,1] provides the largest sum of 6. The method iterates through the array, dynamically calculating the current sum and updating the maximum sum when a larger sum is found. This approach effectively solves the problem with a time complexity of O(n), where n is the length of the array.