Window sliding technique GFG
public class WindowSliding {
// Finding the sum without size of a subArray
public static boolean getSacchai(int[] arr, int givenSum) {
int n = arr.length;
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = i; j < n; j++) {
sum += arr[j];
if(sum == givenSum) {
return true;
}
}
}
return false;
}
// If there is subarray of size k whose sum is equal given sum
public static boolean getTruth(int[] arr, int k, int sum) {
int n = arr.length;
int currentSum = 0;
for(int i = 0; i < k; i++) {
currentSum += arr[i];
}
if(currentSum == sum) {
return true;
}
for(int i = k; i < n; i++) {
currentSum += arr[i] - arr[i - k];
if(currentSum == sum) {
return true;
}
}
return false;
}
// Efficient solution --> Window sliding technique
public static int getMaximum(int[] arr, int k) {
int n = arr.length;
int curr_Sum = 0;
for(int i = 0; i < k; i++) {
curr_Sum += arr[i];
}
int max_Sum = curr_Sum;
for(int i = k; i < n; i++) {
curr_Sum += (arr[i] - arr[i - k]);
max_Sum = Math.max(max_Sum, curr_Sum);
}
return max_Sum;
}
// Naive solution
public static int getMaximumSum(int[] arr, int k) {
int n = arr.length;
int res = Integer.MIN_VALUE;
for(int i = 0; i < n - k; i++) {
int sum = 0;
for(int j = i; j < k + i; j++) {
sum = sum + arr[j];
}
res = Math.max(sum, res);
}
return res;
}
public static void main(String[] args) {
int[] array = {1,8,30,-5,20,7};
System.out.println(getSacchai(array,27));
}
}
Comments
Post a Comment