回答編集履歴
4
ループして最大値を求める個所をメソッド化
test
CHANGED
|
@@ -15,7 +15,7 @@
|
|
|
15
15
|
|
|
16
16
|
int[] a = new int[n];
|
|
17
17
|
int x = (int)Math.sqrt(n);
|
|
18
|
-
int[] r = new int[x+1];
|
|
18
|
+
int[] r = new int[x+1]; //+1 は最期の x 個に満たない分用. 不使用
|
|
19
19
|
|
|
20
20
|
for (int i=0, ii=0; i<n; ii++) {
|
|
21
21
|
r[ii] = Integer.MIN_VALUE;
|
|
@@ -27,21 +27,26 @@
|
|
|
27
27
|
|
|
28
28
|
for (int i=0; i<k; i++) {
|
|
29
29
|
int s = sc.nextInt() - 1; //含む
|
|
30
|
-
int e = sc.nextInt()
|
|
30
|
+
int e = sc.nextInt(); //含まない
|
|
31
31
|
|
|
32
32
|
int rs = (s+x-1) / x; //含む
|
|
33
33
|
int re = e / x; //含まない
|
|
34
34
|
|
|
35
35
|
int v = Integer.MIN_VALUE;
|
|
36
|
-
if(rs >= re) {
|
|
36
|
+
if(rs >= re) {
|
|
37
|
-
|
|
37
|
+
v = max(a, s, e, v);
|
|
38
38
|
} else {
|
|
39
|
-
|
|
39
|
+
v = max(a, s, rs*x, v);
|
|
40
|
-
|
|
40
|
+
v = max(r, rs, re, v);
|
|
41
|
-
|
|
41
|
+
v = max(a, re*x, e, v);
|
|
42
42
|
}
|
|
43
43
|
System.out.println(v);
|
|
44
44
|
}
|
|
45
45
|
}
|
|
46
|
+
//配列 a のインデックス s (含む)から e (含まない)の範囲の値と v のうちの、最大値を返す
|
|
47
|
+
private static int max(int[] a, int s, int e, int v) {
|
|
48
|
+
for(int i=s; i<e; i++) v = Math.max(v, a[i]);
|
|
49
|
+
return v;
|
|
50
|
+
}
|
|
46
51
|
}
|
|
47
52
|
```
|
3
コードコメント追加
test
CHANGED
|
@@ -26,14 +26,14 @@
|
|
|
26
26
|
}
|
|
27
27
|
|
|
28
28
|
for (int i=0; i<k; i++) {
|
|
29
|
-
int s = sc.nextInt() - 1;
|
|
29
|
+
int s = sc.nextInt() - 1; //含む
|
|
30
|
-
int e = sc.nextInt() - 1;
|
|
30
|
+
int e = sc.nextInt() - 1; //含む
|
|
31
31
|
|
|
32
|
-
int rs = (s+x-1) / x;
|
|
32
|
+
int rs = (s+x-1) / x; //含む
|
|
33
|
-
int re = e / x;
|
|
33
|
+
int re = e / x; //含まない
|
|
34
34
|
|
|
35
35
|
int v = Integer.MIN_VALUE;
|
|
36
|
-
if(rs >= re) {
|
|
36
|
+
if(rs >= re) { //この関係なら r は不要
|
|
37
37
|
for(int j=s; j<=e; j++) v = Math.max(v, a[j]);
|
|
38
38
|
} else {
|
|
39
39
|
for(int j=s; j<rs*x; j++) v = Math.max(v, a[j]);
|
2
バグ修正
test
CHANGED
|
@@ -33,9 +33,13 @@
|
|
|
33
33
|
int re = e / x;
|
|
34
34
|
|
|
35
35
|
int v = Integer.MIN_VALUE;
|
|
36
|
+
if(rs >= re) {
|
|
37
|
+
for(int j=s; j<=e; j++) v = Math.max(v, a[j]);
|
|
38
|
+
} else {
|
|
36
|
-
for(int j=s; j<rs*x; j++) v = Math.max(v, a[j]);
|
|
39
|
+
for(int j=s; j<rs*x; j++) v = Math.max(v, a[j]);
|
|
37
|
-
for(int j=rs; j<re; j++) v = Math.max(v, r[j]);
|
|
40
|
+
for(int j=rs; j<re; j++) v = Math.max(v, r[j]);
|
|
38
|
-
for(int j=re*x; j<e; j++) v = Math.max(v, a[j]);
|
|
41
|
+
for(int j=re*x; j<=e; j++) v = Math.max(v, a[j]);
|
|
42
|
+
}
|
|
39
43
|
System.out.println(v);
|
|
40
44
|
}
|
|
41
45
|
}
|
1
コード追加
test
CHANGED
|
@@ -1 +1,43 @@
|
|
|
1
1
|
36～48行目の while は now の加算が if の奥深くに 1 つあるだけですけど、どのような場合でもちゃんとループが終わるでしょうか?
|
|
2
|
+
|
|
3
|
+
---
|
|
4
|
+
1 つのループ内でイロイロ判断するよりも 3 つに分けてやったほうが分かり易い気がします。
|
|
5
|
+
```java
|
|
6
|
+
import java.util.*;
|
|
7
|
+
|
|
8
|
+
public class Main {
|
|
9
|
+
public static void main(String[] args) throws Exception {
|
|
10
|
+
Scanner sc = new Scanner(System.in);
|
|
11
|
+
|
|
12
|
+
int n = 10000;
|
|
13
|
+
|
|
14
|
+
int k = sc.nextInt();
|
|
15
|
+
|
|
16
|
+
int[] a = new int[n];
|
|
17
|
+
int x = (int)Math.sqrt(n);
|
|
18
|
+
int[] r = new int[x+1];
|
|
19
|
+
|
|
20
|
+
for (int i=0, ii=0; i<n; ii++) {
|
|
21
|
+
r[ii] = Integer.MIN_VALUE;
|
|
22
|
+
for (int j=0; j<x && i<n; i++, j++) {
|
|
23
|
+
a[i] = sc.nextInt();
|
|
24
|
+
r[ii] = Math.max(r[ii], a[i]);
|
|
25
|
+
}
|
|
26
|
+
}
|
|
27
|
+
|
|
28
|
+
for (int i=0; i<k; i++) {
|
|
29
|
+
int s = sc.nextInt() - 1;
|
|
30
|
+
int e = sc.nextInt() - 1;
|
|
31
|
+
|
|
32
|
+
int rs = (s+x-1) / x;
|
|
33
|
+
int re = e / x;
|
|
34
|
+
|
|
35
|
+
int v = Integer.MIN_VALUE;
|
|
36
|
+
for(int j=s; j<rs*x; j++) v = Math.max(v, a[j]);
|
|
37
|
+
for(int j=rs; j<re; j++) v = Math.max(v, r[j]);
|
|
38
|
+
for(int j=re*x; j<e; j++) v = Math.max(v, a[j]);
|
|
39
|
+
System.out.println(v);
|
|
40
|
+
}
|
|
41
|
+
}
|
|
42
|
+
}
|
|
43
|
+
```
|