Java Program to Maximum Subarray Sum with Constraints with Explanation
Java
Medium
Collections
28 views
2 min read
272 words
This problem helps you practice core Java fundamentals in a practical way. It builds intuition around subarray, sum, target. Let’s break it down step by step so you can implement it confidently.
Problem Statement
Given an array of integers and a target sum, find the maximum possible sum of a contiguous subarray such that the sum does not exceed the target value. If multiple subarrays have the same maximum sum, return the one with the smallest length. If no such subarray exists, return 0.
Input Format
An integer n (size of array)
Then n integers (array elements, can be positive or negative)
Then an integer target
Output Format
An integer:
• Maximum possible subarray sum ≤ target
• If no such subarray exists, return 0
Constraints
• n ≥ 1
• Subarray must be contiguous
• If multiple subarrays give same max sum, choose the smallest length
• If all subarray sums exceed target, return 0
Concept Explanation
We need the largest sum of any contiguous subarray that
does not exceed the target.
Among equal sums, we prefer the shorter subarray.
Step-by-Step Logic
1.Read array size n, elements, and target.
2.Initialize:
• left = 0
• currentSum = 0
• bestSum = 0
• bestLength = Integer.MAX_VALUE
3.Loop right from 0 to n-1:
•Add arr[right] to currentSum.
4.While currentSum > target and left bestSum:
• Update bestSum.
• Update bestLength.
• Else if currentSum == bestSum and length is smaller:
• Update bestLength.
6.Continue until loop ends.
7.If bestSum is still 0, return 0.
8.Otherwise, return bestSum.
Code Solution
This explanation is written for learning purposes and to help beginners understand the concept clearly.
```java
import java.util.*;
public class MaximumSubarraySum {
public static int maxSubarraySumWithTarget(int[] nums, int target) {
int n = nums.length;
int maxSum = Integer.MIN_VALUE;
// Use sliding window approach with prefix sums
int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
// Use TreeSet to efficiently find the smallest valid prefix sum
TreeSet<Integer> set = new TreeSet<>();
set.add(0);
int result = 0;
for (int i = 1; i <= n; i++) {
// Find the smallest prefix sum such that prefixSum[i] - prefixSum[j] <= target
Integer ceiling = set.ceiling(prefixSum[i] - target);
if (ceiling != null) {
int currentSum = prefixSum[i] - ceiling;
result = Math.max(result, currentSum);
}
set.add(prefixSum[i]);
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int target = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
int result = maxSubarraySumWithTarget(arr, target);
System.out.println(result);
scanner.close();
}
}
```
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Solution Guide
Problem
Given an array of integers and a target sum, find the maximum possible sum of a contiguous subarray such that the sum does not exceed the target value. If multiple subarrays have the same maximum sum, return the one with the smallest length. If no such subarray exists, return 0.
Input / Output
Input
An integer n (size of array)
Then n integers (array elements, can be positive or negative)
Then an integer target
Output
An integer:
• Maximum possible subarray sum ≤ target
• If no such subarray exists, return 0
Constraints
• n ≥ 1
• Subarray must be contiguous
• If multiple subarrays give same max sum, choose the smallest length
• If all subarray sums exceed target, return 0
Explanation
Concept Explanation
We need the largest sum of any contiguous subarray that
does not exceed the target.
Among equal sums, we prefer the shorter subarray.
Step-by-Step Explanation
1.Read array size n, elements, and target.
2.Initialize:
• left = 0
• currentSum = 0
• bestSum = 0
• bestLength = Integer.MAX_VALUE
3.Loop right from 0 to n-1:
•Add arr[right] to currentSum.
4.While currentSum > target and left bestSum:
• Update bestSum.
• Update bestLength.
• Else if currentSum == bestSum and length is smaller:
• Update bestLength.
6.Continue until loop ends.
7.If bestSum is still 0, return 0.
8.Otherwise, return bestSum.
Details
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Official Solution
```java
import java.util.*;
public class MaximumSubarraySum {
public static int maxSubarraySumWithTarget(int[] nums, int target) {
int n = nums.length;
int maxSum = Integer.MIN_VALUE;
// Use sliding window approach with prefix sums
int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
// Use TreeSet to efficiently find the smallest valid prefix sum
TreeSet<Integer> set = new TreeSet<>();
set.add(0);
int result = 0;
for (int i = 1; i <= n; i++) {
// Find the smallest prefix sum such that prefixSum[i] - prefixSum[j] <= target
Integer ceiling = set.ceiling(prefixSum[i] - target);
if (ceiling != null) {
int currentSum = prefixSum[i] - ceiling;
result = Math.max(result, currentSum);
}
set.add(prefixSum[i]);
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int target = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
int result = maxSubarraySumWithTarget(arr, target);
System.out.println(result);
scanner.close();
}
}
```
Solutions (0)
No solutions submitted yet. Be the first!
