Range Query for Largest Sum Contiguous Subarray in Java
A range query for finding the largest sum contiguous subarray in Java is identifying the maximum sum of elements within a specified range of indices in an array. The problem of finding the largest sum contiguous subarray involves identifying a contiguous subarray (a subsequence of adjacent elements) within an array that has the maximum sum of its elements.
Example 1
Input: arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4}
Range = {2, 6}
Output: 6
Explanation: Finding the largest sum contiguous subarray within range {2, 6} of the array· The subarray {-3, 4, -1, 2, 1} is 6.
Example 2
Input: arr = { -1, -2, -3, -4, -5}
Range = {1, 3}
Output: -2
Explanation: Finding the largest sum contiguous subarray within range {1, 3} of the array· The subarray {-2, -3, -4} is -2.
Approach 1: Using Brute Force
The Brute Force approach makes it easy to implement the range query largest sum contiguous subarray. This approach involves iterating through all possible subarrays within the given range and calculating their sums to find the maximum sum.
Algorithm
Step 1: The method takes an array of nums, a starting index start, and an ending index end as input parameters.
Step 2: It first validates the input range to ensure it falls within the bounds of the array.
Step 3: It initializes a variable maxSum to store the maximum sum found so far, initially set to Integer.MIN_VALUE.
Step 4: It iterates through all possible subarrays within the specified range using nested loops.
Step 5: For each starting index i, it calculates the sum of all subarrays starting from i to end.
Step 6: It updates maxSum to be the maximum of its current value and the sum of the current subarray.
Step 7: After iterating through all possible subarrays, it returns the maximum sum found.
Filename: LargestSumSubarrayUsingBruteForce.java
public class LargestSumSubarrayUsingBruteForce {
public static int maxSubArrayInRange(int[] nums, int start, int end) {
// Check for invalid range
if (start < 0 || end >= nums.length || start > end) {
throw new IllegalArgumentException("Invalid range");
}
// Initialize variable to store the maximum sum
int maxSum = Integer.MIN_VALUE;
// Iterate through all possible subarrays within the specified range
for (int i = start; i <= end; i++) {
int sum = 0;
for (int j = i; j <= end; j++) {
// Calculate the sum of the current subarray
sum += nums[j];
// Update maxSum if the sum of the current subarray is greater
maxSum = Math.max(maxSum, sum);
}
}
// Return the maximum sum contiguous subarray within the specified range
return maxSum;
}
public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int start = 2;
int end = 6;
// Find the largest sum contiguous subarray within the range [start, end]
int maxSum = maxSubArrayInRange(nums, start, end);
// Print the result
System.out.println("Largest sum contiguous subarray within range [" + start + ", " + end + "]: " + maxSum);
}
}
Output
Largest sum contiguous subarray within range [2, 6]: 6
Time Complexity: The time complexity of the brute force approach is O(n^2), where n is the size of the input array. This is because it involves two nested loops to iterate through all possible subarrays within the specified range.
Space Complexity: The space complexity of the brute force approach is O(1) as it only requires a constant amount of extra space for storing variables like maxSum, sum, and loop indices.
Approach 2: Dynamic Programming – Kadene’s Algorithm
The Largest Sum Contiguous subarray can be implemented through Kadene’s Algorithm. This algorithm efficiently solves the problem by iterating through the array once and dynamically updating the maximum sum and current sum as it traverses the elements within the specified range.
Algorithm
Step 1: The method takes an array of nums, a starting index start, and an ending index end as input parameters.
Step 2: It first validates the input range to ensure it falls within the bounds of the array.
Step 3: It initializes two variables: maxSum to store the maximum sum found so far and currentSum to store the sum of the current subarray being considered, both initialized to the value at the starting index.
Step 4: It iterates through the array from the index start + 1 to end.
Step 5: For each element, it updates currentSum to be the maximum of the current element and the sum of the current element and the previous currentSum.
Step 6: It updates maxSum to be the maximum of maxSum and currentSum at each iteration.
Step 7: After iterating through all elements within the specified range, it returns maxSum, which represents the largest sum contiguous subarray within the range.
Filename: LargestSumSubarrayUsingKadenes.java
public class LargestSumSubarrayUsingKadenes {
public static int maxSubArrayInRange(int[] nums, int start, int end) {
// Check for invalid range
if (start < 0 || end >= nums.length || start > end) {
throw new IllegalArgumentException("Invalid range");
}
// Initialize maxSum and currentSum with the value at start index
int maxSum = nums[start];
int currentSum = nums[start];
// Iterate through the range, applying Kadane's algorithm
for (int i = start + 1; i <= end; i++) {
// Update currentSum to be the maximum of nums[i] or currentSum + nums[i]
currentSum = Math.max(nums[i], currentSum + nums[i]);
// Update maxSum to be the maximum of its current value and currentSum
maxSum = Math.max(maxSum, currentSum);
}
// Return the maximum sum contiguous subarray within the specified range
return maxSum;
}
public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int start = 2;
int end = 6;
// Find the largest sum contiguous subarray within the range [start, end]
int maxSum = maxSubArrayInRange(nums, start, end);
// Print the result
System.out.println("Largest sum contiguous subarray within range [" + start + ", " + end + "]: " + maxSum);
}
}
Output
Largest sum contiguous subarray within range [2, 6]: 6
Time Complexity: The time complexity of Kadane's algorithm is O(n), where n is the size of the input array. This is because the algorithm iterates through the array only once, calculating the maximum sum subarray efficiently.
Space Complexity: The space complexity of Kadane's algorithm is O(1) as it only requires a constant amount of extra space for storing variables like maxSum, currentSum, and loop indices.
Approach 3: Divide and Conquer
To find the largest sum contiguous subarray within a specified range using the Divide and Conquer approach. This approach efficiently solves the problem by recursively dividing the array into smaller subproblems, finding the maximum sum subarray within each subproblem, and then combining the results to find the maximum sum subarray across the entire array.
Algorithm
Step 1: The method takes an array nums, a starting index start, and an ending index end as input parameters.
Step 2: It first validates the input range to ensure it falls within the bounds of the array.
Step 3: It calls the maxSubArrayHelper method with the input array nums, starting index start, and ending index end.
Step 4: Another method is a recursive function that takes an array nums, a left index left, and a right index right as input parameters.
Step 5: If the left index is equal to the right index (base case), it returns the value of the element at that index.
Step 6: Otherwise, it calculates the middle index mid as the average of left and right.
Step 7: It recursively calls method to find the maximum sum subarray in the left half (left to mid) and the right half (mid + 1 to right) of the array.
Step 8: It calculates the maximum sum subarray that crosses the middle index mid using the method.
Step 9: It returns the maximum of the maximum sum subarrays found in the left half, right half, and the crossing subarray.
Filename: LargestSumSubarrayUsingDivideandConquer.java
public class LargestSumSubarrayUsingDivideandConquer {
public static int maxSubArrayInRange(int[] nums, int start, int end) {
// Check for invalid range
if (start < 0 || end >= nums.length || start > end) {
throw new IllegalArgumentException("Invalid range");
}
// Call the helper function to perform the divide and conquer
return maxSubArrayHelper(nums, start, end);
}
private static int maxSubArrayHelper(int[] nums, int left, int right) {
// Base case: if left index equals the right index, return the element at that index
if (left == right) {
return nums[left];
}
// Calculate the middle index
int mid = left + (right - left) / 2;
// Recursively find the maximum sum contiguous subarrays for left and right halves
int leftMax = maxSubArrayHelper(nums, left, mid);
int rightMax = maxSubArrayHelper(nums, mid + 1, right);
// Find the maximum sum contiguous subarray crossing the middle index
int crossingMax = maxCrossingSum(nums, left, mid, right);
// Return the maximum of leftMax, rightMax, and crossingMax
return Math.max(Math.max(leftMax, rightMax), crossingMax);
}
private static int maxCrossingSum(int[] nums, int left, int mid, int right) {
// Initialize variables to store the maximum sum of left and right subarrays
int leftSum = Integer.MIN_VALUE;
int sum = 0;
// Find the maximum sum of the left subarray
for (int i = mid; i >= left; i--) {
sum += nums[i];
leftSum = Math.max(leftSum, sum);
}
// Reset sum for calculating the maximum sum of the right subarray
sum = 0;
int rightSum = Integer.MIN_VALUE;
// Find the maximum sum of the right subarray
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
rightSum = Math.max(rightSum, sum);
}
// Return the sum of the maximum sums of left and right subarrays
return leftSum + rightSum;
}
public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int start = 2;
int end = 6;
// Find the largest sum contiguous subarray within the range [start, end]
int maxSum = maxSubArrayInRange(nums, start, end);
// Print the result
System.out.println("Largest sum contiguous subarray within range [" + start + ", " + end + "]: " + maxSum);
}
}
Output
Largest sum contiguous subarray within range [2, 6]: 6
Time Complexity: The time complexity of the Divide and Conquer approach is O(nlogn), where n is the size of the input array. This is because the array is recursively divided into halves, and each recursive call takes O(n) time to compute the maximum sum subarray crossing the middle index.
Space Complexity: The space complexity of the Divide and Conquer approach is O(logn) due to the recursive calls on the stack, where n is the size of the input array.
Approach 4: Prefix Sum Technique
The Prefix Sum Technique makes it easy to implement the range query largest sum contiguous subarray. This approach efficiently solves the problem by maintaining the prefix sum of elements up to each index in the array· By subtracting the minimum prefix sum encountered so far from the current prefix sum, we can find the largest sum contiguous subarray.
Algorithm
Step 1: Initialize variables maxSum, minPrefixSum, and prefixSum to store the maximum sum, the minimum prefix sum, and the current prefix sum, respectively. Set maxSum to Integer·MIN_VALUE, minPrefixSum to 0, and prefixSum to 0.
Step 2: Iterate through the array from the starting index start to the ending index end.
Step 3: At each iteration, update prefixSum by adding the current element to it.
Step 4: Update maxSum to be the maximum of its current value and the difference between prefixSum and minPrefixSum.
Step 5: Update minPrefixSum to be the minimum of its current value and prefixSum.
Step 6: After iterating through the specified range, maxSum will contain the largest sum contiguous subarray.
Step 7: Return maxSum as the result.
Filename: LargestSumSubarrayUsingPrefix.java
public class LargestSumSubarrayUsingPrefix {
public static int maxSubArrayInRange(int[] nums, int start, int end) {
// Check for invalid range
if (start < 0 || end >= nums.length || start > end) {
throw new IllegalArgumentException("Invalid range");
}
// Initialize variables to store maximum sum, minimum prefix sum, and current prefix sum
int maxSum = Integer.MIN_VALUE;
int minPrefixSum = 0;
int prefixSum = 0;
// Iterate through the range to compute prefix sums and update maxSum
for (int i = start; i <= end; i++) {
// Calculate prefix sum up to index i
prefixSum += nums[i];
// Update maxSum by subtracting the minimum prefix sum encountered so far
maxSum = Math.max(maxSum, prefixSum - minPrefixSum);
// Update minPrefixSum to be the minimum of its current value and prefixSum
minPrefixSum = Math.min(minPrefixSum, prefixSum);
}
// Return the maximum sum contiguous subarray within the specified range
return maxSum;
}
public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int start = 2;
int end = 6;
// Find the largest sum contiguous subarray within the range [start, end]
int maxSum = maxSubArrayInRange(nums, start, end);
// Print the result
System.out.println("Largest sum contiguous subarray within range [" + start + ", " + end + "]: " + maxSum);
}
}
Output
Largest sum contiguous subarray within range [2, 6]: 6
Time Complexity: The time complexity of the Prefix Sum approach is O(n), where n is the size of the input array. This is because it involves a single pass through the array to compute the prefix sum and update the maximum sum.
Space Complexity: The space complexity is O(1) because the algorithm only requires a constant amount of extra space for variables. It does not require additional space proportional to the input size.
Approach 5: Sliding Window Technique
The different approach for finding the largest sum contiguous subarray is the "Sliding Window" technique. This approach maintains a window that slides through the array, continuously updating the sum of elements within the window. At each step, the window expands to the right if adding the next element increases the sum, and contracts from the left if removing the leftmost element increases the sum. This way, it efficiently finds the maximum sum contiguous subarray without the need for nested loops or recursion.
Algorithm
Step 1: Initialize two pointers: left and right, both pointing to the start of the array.
Step 2: Initialize variables maxSum and currentSum to store the maximum sum and the current sum of elements within the window, respectively. Set both to zero initially.
Step 3: While the right pointer is within the bounds of the array:
Step 3.1: Add the element at the right pointer to the currentSum.
Step 3.2: If currentSum becomes negative, reset it to zero (because a negative sum does not contribute to finding the largest sum contiguous subarray).
Step 3.3: Update maxSum to be the maximum of its current value and currentSum.
Step 4: Increment the right pointer to expand the window.
Step 5: Return maxSum as the result.
Filename: LargestSumSubarrayUsingSlidingWindow.java
public class LargestSumSubarrayUsingSlidingWindow {
public static int maxSubArray(int[] nums) {
// Check for null or empty input array
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("Input array is empty or null");
}
// Initialize variables for maximum sum and current sum
int maxSum = 0;
int currentSum = 0;
// Iterate through the array using a sliding window
for (int left = 0, right = 0; right < nums.length; right++) {
// Add the current element to the current sum
currentSum += nums[right];
// Update maxSum if currentSum is greater
maxSum = Math.max(maxSum, currentSum);
// Shrink the window if currentSum becomes negative
while (currentSum < 0 && left <= right) {
currentSum -= nums[left++];
}
}
// Return the maximum sum contiguous subarray
return maxSum;
}
public static int maxSubArrayInRange(int[] nums, int start, int end) {
// Check for invalid range
if (start < 0 || end >= nums.length || start > end) {
throw new IllegalArgumentException("Invalid range");
}
// Create a subarray within the specified range
int[] subarray = new int[end - start + 1];
System.arraycopy(nums, start, subarray, 0, subarray.length);
// Find the maximum sum contiguous subarray in the subarray
return maxSubArray(subarray);
}
public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int start = 2;
int end = 6;
// Find the largest sum contiguous subarray within the range [start, end]
int maxSum = maxSubArrayInRange(nums, start, end);
// Print the result
System.out.println("Largest sum contiguous subarray within range [" + start + ", " + end + "]: " + maxSum);
}
}
Output
Largest sum contiguous subarray within range [2, 6]: 6
Time Complexity: The time complexity of the Sliding Window approach is O(n), where n is the size of the input array. This is because it involves a single pass through the array.
Space Complexity: The space complexity is O(1) because the algorithm only requires a constant amount of extra space for variables.