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.
Comments
Post a Comment
Leave Comment