Day 007 | 全探索（ブルートフォース）

問題

N個の整数からなる数列 A が与えられます。数列から 2つの要素を選んで その積が最大になるようにしてください。選ぶ2つの要素は 異なるインデックス のものとします（同じ要素の値が同じでも構いません）。

入力形式

N
A_1 A_2 ... A_N

制約

$2 \le N \le 1000$

$-1000 \le A_i \le 1000$

整数

入出力例

入力例 1

4
3 -1 -5 2

出力例 1

入力例 2

3
1 2 3

出力例 2

入力例 3

2
-3 -4

出力例 3

ヒント (段階的開示)

ヒント1: 方向性

「全探索」= ありうる全ての組み合わせを試して最大値を求める。2つを選ぶ全ペアを試そう。

ヒント2: アプローチ

i < j となる全 (i, j) ペアを二重ループで列挙。N=1000 で約50万通り → Pythonでも余裕。

ヒント3: 誘導

N = int(input())
A = list(map(int, input().split()))

ans = -10**18
for i in range(N):
    for j in range(i + 1, N):
        ans = max(ans, A[i] * A[j])

print(ans)

模範解答 (Python)

N = int(input())
A = list(map(int, input().split()))

ans = -10**18
for i in range(N):
    for j in range(i + 1, N):
        ans = max(ans, A[i] * A[j])

print(ans)

Step-by-Step 解説

1入力の受け取り
1行目で N、2行目で list(map(int, input().split())) で配列化。

2全ペアを二重ループで探索
j = i + 1 から始めることで、同一インデックスと重複ペアの両方を排除できる。

3初期値 -10**18 を使う理由
全要素が負の場合、積が全て負になる可能性がある。ans = 0 だと誤答する。

計算量

二重ループ: $O(N^2)$
N=1000 のとき: 約 500,000 回 ≈ 0.05秒
N=10^6 の場合は O(N^2) は厳しい

よくあるミス

ミス	原因	正しい書き方
`for j in range(N)` + `if i == j: continue`	冗長	`for j in range(i + 1, N)`
`ans = 0` で初期化	負の積を見落とす	`ans = -10*18` または `A[0] A[1]`
`int(input().split())`	splitはリストを返す	`map(int, input().split())`
積でなく和を計算	問題を読み間違い	`A[i] * A[j]`

Day 007 — 全探索（ブルートフォース）

問題