# 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.

`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.