Introduction to algorithms with java-Shakutori method

Article summary

This is a series of articles that I have compiled in my study and memo. The sixth bullet. Click here for previous articles.

In this article

-* Shakutori method *

I will study about. With cumulative sum? Is it the one used? I often see them introduced as a set.

Shakutori method

Like the cumulative sum, it seems to be a technique for speeding up operations on arrays of numbers.

Reference: [[Cumulative sum, shakutori method] Algorithm illustration that even beginners can understand](https://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF% E7% A9% 8D% E5% 92% 8C% E3% 80% 81% E3% 81% 97% E3% 82% 83% E3% 81% 8F% E3% 81% A8% E3% 82% 8A% E6% B3% 95% E3% 80% 91% E5% 88% 9D% E7% B4% 9A% E8% 80% 85% E3% 81% A7% E3% 82% 82% E8% A7% A3% E3% 82% 8B% E3% 82% A2% E3% 83% AB% E3% 82% B4)

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 array of integers of size n. When divided into the length t of the specified interval from there, what is the maximum value of the sum within that interval? It is a problem to solve a typical problem. It's a problem that can be done with cumulative sums. See also the previous article (https://qiita.com/aja_min/items/3a334fb03749d8f42a25).

As an example, consider the case of size 5 (n = 5) and interval length 2 (t = 2).

Consider the array as shown. If you divide this by the length of 2 of the section, it will be as follows.

From the conclusion, 4 + 10 = 14 of the sum when choosing the 4th and 5th is the highest value, but how much is the amount of calculation so far?

1. Which section to select
2. Calculation of sum within the interval

Let's think about it separately.

First of all, 1. How to divide the section, but it's easy. In the above example, the sum is taken four times. If you drop it in the formula, it will be n-t + 1 time. This time 5-2 + 1 = 4 times.

Next is 2. The calculation of the sum within that interval, but we are processing it twice to access each element of the array.

In general, it is (n --t + 1) * t times. Note that if t depends on n, the amount of calculation will be about O (n ^ 2). In this case, if n is taken as 10 ^ 5, it will take a tremendous amount of time. At that time, the Shakutori method was introduced.

Well, it's a relatively simple story ... Remember the sum so that you don't have to add from 1 each time. about it. See the figure below.

Do you understand somehow? Remembering the sum, you don't have to add all the elements t times at a time. The complexity is n-t + 1 times because we 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: AtCoder --abc032-c "column"

N K
s1 
s2
:
sN

This is the problem. It's a little applied. It's basically a shaky method, but this time the length hasn't been decided. We will implement it according to the following policy.

--Save the product in the same way as the Shakutori method. --As long as the conditions are met, proceed to the right end. --When the conditions are no longer met, proceed to the left end. ――When the left end comes to the far right, the search ends. The longest value at that time 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 non-negative integer sequence
		long k = sc.nextLong(); //Maximum product

		long[] s = new long[n]; //Non-negative 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 the answer
		int left = 0; //Left end
		int right = 0; //Right end

		for (left = 0; left < n; left++) {

			//Fix the left edge and move the right edge as far as you can go to multiply
			while (right < n && seki * s[right] <= k) {
				seki *= s[right++];
			}

			//Storage of maximum ans
			ans = right - left;
			if (ans_max < ans) {
				ans_max = ans;
			}

			//Move the left edge. left==Be careful when it becomes right.
			if (left == right) {
				right++;
			} else {
				seki /= s[left];
			}

		}

		System.out.println(ans_max);
	}
}

Yes. I referred to various sources, but it was quite difficult. .. The example where left catches up with right was especially difficult. This also seems to require practice. .. .. Let's practice well. I will read the source over and over again.

see you!