Maximum Good Subarray Sum in Java
The maximum good subarray sum problem aims to efficiently count and analyze "good" subarrays within a numeric array, revealing the interplay between array elements and their absolute differences.
In the input, an array of length n and a positive integer k are given.
When the difference between the first and last element of a subarray of nums is exactly k, it is said to be good. In simpler terms, the subarray nums[i..j] is good if nums[i] - nums[j] == k.
Example 1:
Input: nums = [1, 2, 3, 4, 5, 6], k = 1
Output: 11
Explanation: A good subarray has an absolute difference of 1 between the first and last elements. The following are all good subarrays: [1,2], [2,3], [3,4], [4,5], and [5,6]. For the subarray, the maximum subarray sum is 11 [5,6].
Example 2:
Input: nums = [-1, -2, -3, -4], k = 3
Output: -6
Explanation: A good subarray has an absolute difference of two between the first and last element. The subarrays [-1,-2,-3] and [-2,-3,-4] are all good choices. For the subarray [-1,-2,-3], the maximum subarray sum is -6.
Using Naive Approach
The naive approach to finding the maximum subarray sum with an absolute difference of `k` uses three nested loops. The outer loop iterates through all possible subarrays, the middle loop iterates through all possible ending indices, and the inner loop calculates the sum of elements within the subarray. If the absolute difference is equal to `k,` the algorithm updates the maximum subarray sum. The algorithm continues iterating through all possible subarrays, resulting in the maximum subarray sum.
Here’s the implementation of finding the maximum good subarray sum using a naive approach :
FileName:NaiveSolution.java
public class NaiveSolution {
// Method to find the maximum subarray sum with an absolute difference of 'k' between the first and last elements
public long maximumSubarraySum(int[] nums, int k) {
// Get the length of the input array
int n = nums.length;
long ans = Long.MIN_VALUE;
for (int i = 0; i < n; ++i) {
long sum = 0;
for (int j = i; j < n; ++j) {
// Add the current element to the sum
sum += nums[j];
// Check if the absolute difference between the first and last elements is equal to 'k'
if (Math.abs(nums[i] - nums[j]) == k) {
// Update the maximum subarray sum if the current sum is greater
ans = Math.max(ans, sum);
}
}
}
// If no valid subarray is found, return 0; otherwise, return the maximum subarray sum
return ans == Long.MIN_VALUE ? 0 : ans;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6};
int k = 1;
NaiveSolution solution = new NaiveSolution();
long result = solution.maximumSubarraySum(nums, k);
System.out.println("Maximum Subarray Sum: " + result);
}
}
Output:
Maximum Subarray Sum: 11
Complexity analysis: The naive approach to finding the maximum subarray sum with an absolute difference of `k` is O(n^3), with iterations of O(n) for each possible starting index, middle loop, and inner loop. The overall time complexity is O(n^3) due to nested loops, while the space complexity is O(1) due to constant extra space usage.
Using Optimized approach
The optimized approach aims to find the maximum subarray sum with a difference of at most `k` between elements using a `HashMap` named `prefixSumMap.` The code initializes the `prefixSumMap,` iterates through the array, updates the current prefix sum, and stores the final result in `maxSubarraySum.` The above method is an efficient approach that reduces redundant computations and improves algorithm time complexity.
Here’s the implementation of finding the maximum good subarray sum using the optimized approach:
FileName:SolutionOptimized.java
import java.util.HashMap;
import java.util.Map;
public class SolutionOptimized {
// Method to find the maximum subarray sum where the difference between
// any two elements in the subarray are either equal to or less than 'k.'
public long maximumSubarraySum(int[] nums, int k) {
// Map to store the prefix sum and its corresponding index.
Map<Integer, Long> prefixSumMap = new HashMap<>();
// Initialize the map with the first element's value and index.
prefixSumMap.put(nums[0], 0L);
long runningSum = 0;
int n = nums.length;
long maxSubarraySum = Long.MIN_VALUE;
for (int i = 0; i < n; ++i) {
runningSum += nums[i];
// Check if there is a prefix sum that, when subtracted from the current
// running sum equals 'k.' If yes, update the maximum subarray sum.
if (prefixSumMap.containsKey(nums[i] - k)) {
maxSubarraySum = Math.max(maxSubarraySum, runningSum - prefixSumMap.get(nums[i] - k));
}
// Check if there is a prefix sum that, when added to the current
// running sum equals 'k'. If yes, update the maximum subarray sum.
if (prefixSumMap.containsKey(nums[i] + k)) {
maxSubarraySum = Math.max(maxSubarraySum, runningSum - prefixSumMap.get(nums[i] + k));
}
// Update the prefix sum map with the current running sum if:
// 1. The next element is not already present in the map, or
// 2. The next element is present, but its corresponding prefix sum is less than the current running sum.
if (i + 1 < n && (!prefixSumMap.containsKey(nums[i + 1]) || prefixSumMap.get(nums[i + 1]) > runningSum)) {
prefixSumMap.put(nums[i + 1], runningSum);
}
}
// If no valid subarray is found, return 0. Otherwise, return the maximum subarray sum.
return maxSubarraySum == Long.MIN_VALUE ? 0 : maxSubarraySum;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6};
int k = 1;
SolutionOptimized solution = new SolutionOptimized();
long result = solution.maximumSubarraySum(nums, k);
System.out.println("Maximum Subarray Sum: " + result);
}
}
Output:
Maximum Subarray Sum: 11
Complexity analysis: O(N) is the time complexity of the above approach, where N is the input array's length in digits. The array is iterated through once by the code. O(N) is the space complexity, where N is the input array nums' length.