[Java] Introduction to algorithms in javascooping method
Article summary
This is a series of articles that I have collected in my study and memo. Sixth bullet. Click here for previous articles.
In this article

 Scooping method *
Study about With cumulative sum? Is it the one used? I often see them introduced in the set.
Scooping method
Like cumulative sums, it seems to be a technique to speed up operations on arrays of numbers.
Reference: [Cumulative sum, Shakutori method] Algorithm illustration that even beginners can understand
Well… it’s a bit confusing if you look at the link. .. .. I will explain it for my own study.
As an example, consider an integer array of size n. What is the maximum value of the sum in that interval when it is divided into the specified interval length t? It is a problem that solves a general problem. It is a problem that can be done with cumulative sum. See also previous article.
As an example, consider a size of 5 (n = 5) and an interval length of 2 (t = 2).
Consider the array as shown. If you divide this by the length of the interval, it will be as follows.
From the conclusion, the sum of 4 + 10 = 14 when choosing the 4th and 5th is the highest value, but how much calculation is so far?
 Which section to select
 Calculation of the sum within that section
Let’s divide it into two parts.
First of all, 1. How to divide the section is easy. In the above example, the sum is summed four times. If you drop it into the formula, it becomes nt + 1 times. This time 52 + 1 = 4 times.
Next is 2. Calculation of the sum within that interval, but it is processed twice each to access each element of the array.
In total, (nt + 1) * t times. If t is dependent on n, the amount of calculation will be about O(n^2), so be careful. In this case, if n is taken as 10^5, it will take a very long time. That’s when the scooping method came into play.
Well, it’s a relatively simple story, but… Please remember the sum and do not have to add from 1 each time. about it. See the figure below.
Do you understand it somehow? Remembering the sum, you don’t have to add all the elements t times. The complexity is nt + 1 times, because you no longer need to access each element of the array. I think it can be expressed as O(n).
Let’s go to the example.
Example
Example: AtCoderabc032c “column”
Click here for question texts/input examples, etc.
*Please refer to the problem link as much as possible
This is the problem. It is a little applied. Basically, it’s a scooping method, but this time the length is not fixed. It will be implemented according to the following policy.
 Save the product as you would for the scooping method.
 Proceed to the right end as long as the conditions are met.
 If the condition is no longer met, move to the left end.
 When the left end reaches the far right, the search ends. The longest value at that point is output.
Below is an example answer.
Main.java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // length of nonnegative integer sequence
long k = sc.nextLong(); // maximum product
long[] s = new long[n]; // nonnegative integer sequence
for (int i = 0; i <n; i++) {
s[i] = sc.nextLong();
if (s[i] == 0l) {
System.out.println(n);
return;
}
}
long seki = 1; // Variable storing the product
int ans = 0; // maximum length
int ans_max = 1; // save answer
int left = 0; // left edge
int right = 0; // right edge
for (left = 0; left <n; left++) {
// Fix the left end, move the right end until you can go to multiplication
while (right <n && seki * s[right] <= k) {
seki *= s[right++];
}
// store the maximum value of ans
ans = rightleft;
if (ans_max <ans) {
ans_max = ans;
}
// Move the left end. Be careful when left == right.
if (left == right) {
right++;
} else {
seki /= s[left];
}
}
System.out.println(ans_max);
}
}
Yes. I referred to various sources, but it was difficult. .. It was especially difficult for left to catch up with right. It seems that this also requires practice. .. .. Let’s practice well. I will try to read the source over and over again.
see you!