paiza プログラミング

[Ruby|Python]paiza 累積和メニュー2 【連続するN個の和の最大値】

今回はpaiza 累積和メニューセクショ2【連続する N 個の和の最大値】を解説します。

n個の整数の要素からなる配列aがあり、その中で連続する k個の整数の和が最大の値はいくつか？を出力する問題です。

本記事で使用しているアルゴリズムやメソッドについて

解答例で使っているアルゴリズムやメソッドについて、下記の記事で詳しく解説していますので参考にしてみて下さい。

累積和メニュー2：【連続するN個の和の最大値】

2-STEP1: 連続する N 個の和の最大値 1 (paizaランク C 相当)

a[0]からa[9]まで10個の整数を要素に持つ配列 a=[1, 5, 9, 7, 5, 3, 2, 5, 8, 4] で、連続する3個の整数の和の最大値を累積和で求め、出力する問題です。

a[0] + a[1] + a[2] = 1 + 5 + 9 = 15
a[1] + a[2] + a[3] = 5 + 9 + 7 = 21 ← 最大！
a[2] + a[3] + a[4] = 9 + 7 + 5 = 21 ← 最大！
a[3] + a[4] + a[5] = 7 + 5 + 3 = 15
a[4] + a[5] + a[6] = 5 + 3 + 2 = 10
a[5] + a[6] + a[7] = 3 + 2 + 5 = 10
a[6] + a[7] + a[8] = 2 + 5 + 8 = 15
a[7] + a[8] + a[9] = 5 + 8 + 4 = 15

答えは 21

これを累積和を使って求める問題です。

Ruby解答例1

配列a の累積和s を求めた後に、要素３個分の区間和を次々と求めて最大和を更新していきます。
配列aのループと累積和sのループを回すことになりますが、コードは読みやすいです。

# 入力
k = 3
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]

# 累積和
s = [0]
a.each { |num| s << s[-1] + num }

# 連続する3個の最大和を調べる
max_sum = 0
k.upto(a.length) do |i|
  # 今までの最大和より大きければ更新
  section_sum = s[i] - s[i - k]
  max_sum = [max_sum, section_sum].max
end

# 連続する3個の最大和を出力
puts max_sum

 

Ruby解答例2

配列a の累積和s を求めながら、3個目の要素から３個分の区間和を求めて最大和を更新していきます。
配列aのループ1回で済みますが、ちょっと中身が複雑になります。

# 入力
k = 3
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]

# 累積和と最大区間和の更新
max_sum = 0
s = [0]
a.each_with_index do |num, i|
  # 累積和更新
  s << s[-1] + num
  # 3個目の要素からは区間和を調べる
  if i >= k - 1
    # 区間和が最大なら更新
    max_sum = [max_sum, s[-1] - s[i - (k - 1)]].max
  end
end

# 連続する3個の和の最大値を出力
puts max_sum

 

Python解答例1

配列a の累積和s を求めた後に、要素３個分の区間和を次々と求めて最大和を更新していきます。
配列aのループと累積和sのループを回すことになりますが、コードは読みやすいです。

# 入力
k = 3
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]

# 累積和
s = [0]
for num in a:
    s.append(s[-1] + num)

# 連続する3個の最大和を調べる
max_sum = 0
for i in range(k, len(a) + 1):
    # 今までの最大和より大きければ更新
    section_sum = s[i] - s[i - k]
    max_sum = max([max_sum, section_sum])

# 連続する3個の最大和を出力
print(max_sum)

 

Python解答例2

配列a の累積和s を求めながら、3個目の要素から３個分の区間和を求めて最大和を更新していきます。
配列aのループ1回で済みますが、ちょっと中身が複雑になります。

# 入力
k = 3
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]

# 累積和と最大区間和の更新
max_sum = 0
s = [0]
for i, num in enumerate(a):
    # 累積和更新
    s.append(s[-1] + num)
    # 3個目の要素からは区間和を調べる
    if i >= k - 1:
        # 区間和が最大なら更新
        max_sum = max([max_sum, s[-1] - s[i - (k - 1)]])

# 連続する3個の和の最大値を出力
print(max_sum)

 

2-STEP2: 連続する N 個の和の最大値 2 (paizaランク C 相当)

a[0]からa[9]まで10個の整数を要素に持つ配列 a が 半角スペース区切りで与えられ、連続する3個の整数の和の最大値を累積和で求め、出力する問題です。

与えられる条件は以下の通りです。

  • 1 ≦ a_i ≦ 100 (0 ≦ i ≦ 9)
入出力例

INPUT1の例
a[7] + a[8] + a[9] = 7 + 8 + 9 = 27 が最大なので 27 を出力

INPUT2の例
a[7] + a[8] + a[9] = 1 + 8 + 8 = 17 が最大なので 17 を出力

INPUT1 = <<"EOS"
1 2 3 4 5 6 7 8 9 10
EOS
OUTPUT1 = <<"EOS"
27
EOS

INPUT2 = <<"EOS"
8 1 3 1 3 8 3 1 8 8
EOS
OUTPUT2 = <<"EOS"
17
EOS

 

Ruby解答例1

配列aの要素を受け取る処理を追加します。あとはSTEP1-解答例1と同じです。

# 入力
k = 3
a = gets.split.map(&:to_i)

# 累積和
s = [0]
a.each { |num| s << s[-1] + num }

# 連続する3個の最大和を調べる
max_sum = 0
k.upto(a.length) do |i|
  # 今までの最大和より大きければ更新
  section_sum = s[i] - s[i - k]
  p section_sum
  max_sum = [max_sum, section_sum].max
end

# 連続する3個の最大和を出力
puts max_sum

 

Ruby解答例2

配列aの要素を受け取る処理を追加します。あとはSTEP1-解答例2と同じです。

# 入力
k = 3
a = gets.split.map(&:to_i)

# 累積和と最大区間和の更新
max_sum = 0
s = [0]
a.each_with_index do |num, i|
  # 累積和更新
  s << s[-1] + num
  # 3個目の要素からは区間和を調べる
  if i >= k - 1
    # 区間和が最大なら更新
    max_sum = [max_sum, s[-1] - s[i - (k - 1)]].max
  end
end

# 連続する3個の最大和を出力
puts max_sum

 

Python解答例1

配列aの要素を受け取る処理を追加します。あとはSTEP1-解答例1と同じです。

# 入力
k = 3
a = list(map(int, input().split()))

# 累積和
s = [0]
for num in a:
    s.append(s[-1] + num)

# 連続する3個の最大和を調べる
max_sum = 0
for i in range(k, len(a) + 1):
    # 今までの最大和より大きければ更新
    section_sum = s[i] - s[i - k]
    max_sum = max([max_sum, section_sum])

# 連続する3個の最大和を出力
print(max_sum)

 

Python解答例2

配列aの要素を受け取る処理を追加します。あとはSTEP1-解答例2と同じです。

# 入力
k = 3
a = list(map(int, open(0).read().split()))

# 累積和と最大区間和の更新
max_sum = 0
s = [0]
for i, num in enumerate(a):
    # 累積和更新
    s.append(s[-1] + num)
    # 3個目の要素からは区間和を調べる
    if i >= k - 1:
        # 区間和が最大なら更新
        max_sum = max([max_sum, s[-1] - s[i - (k - 1)]])

# 連続する3個の和の最大値を出力
print(max_sum)

 

2-STEP3: 連続する N 個の和の最大値 3 (paizaランク C 相当)

1行目で要素数 n、2行目で10個の整数 a[0], a[1] ... a[9] が半角スペース区切りで与えられ、連続する3個の整数の和の最大値を累積和で求め、出力する問題です。

与えられる条件は以下の通りです。

  • 3 ≦ n ≦ 100
  • 1 ≦ a_i ≦ 100 (0 ≦ i ≦ 9)
入出力例

INPUT1の例
a[7] + a[8] + a[9] = 7 + 8 + 9 = 27 が最大なので 27 を出力

INPUT2の例
a[1] + a[2] + a[3] = 81 + 31 + 83 = 195 が最大なので 195 を出力

INPUT1 = <<"EOS"
10
1 2 3 4 5 6 7 8 9 10
EOS
OUTPUT1 = <<"EOS"
27
EOS

INPUT2 = <<"EOS"
8
13 81 31 83 38 11 33 88
EOS
OUTPUT2 = <<"EOS"
195
EOS

 

Ruby解答例1

入力1行目の要素数nは使わないので捨てて、2行目から配列aの値を受け取ります。あとはSTEP2-解答例1と同じです。

# 入力
k = 3
gets
a = gets.split.map(&:to_i)

# 累積和
s = [0]
a.each { |num| s << s[-1] + num }

# 連続する3個の最大和を調べる
max_sum = 0
k.upto(a.length) do |i|
  # 今までの最大和より大きければ更新
  section_sum = s[i] - s[i - k]
  max_sum = [max_sum, section_sum].max
end

# 連続する3個の最大和を出力
puts max_sum

 

Ruby解答例2

$stdin.read で入力を一括で受け取り、多重代入しています。あとはSTEP2-解答例2と同じです。（入力終了は ctrl+d）

# 入力
k = 3
_, *a = $stdin.read.split.map(&:to_i)

# 累積和と最大区間和の更新
max_sum = 0
s = [0]
a.each_with_index do |num, i|
  # 累積和更新
  s << s[-1] + num
  # 3個目の要素からは区間和を調べる
  if i >= k - 1
    # 区間和が最大なら更新
    max_sum = [max_sum, s[-1] - s[i - (k - 1)]].max
  end
end

# 連続する3個の最大和を出力
puts max_sum

 

Python解答例1

入力1行目の要素数nは使わないので捨てて、2行目から配列aの値を受け取ります。あとはSTEP2-解答例1と同じです。

# 入力
k = 3
input()
a = list(map(int, input().split()))

# 累積和
s = [0]
for num in a:
    s.append(s[-1] + num)

# 連続する3個の最大和を調べる
max_sum = 0
for i in range(k, len(a) + 1):
    # 今までの最大和より大きければ更新
    section_sum = s[i] - s[i - k]
    max_sum = max([max_sum, section_sum])

# 連続する3個の最大和を出力
print(max_sum)

 

Python解答例2

open(0).read() で入力を一括で受け取り、多重代入しています。あとはSTEP2-解答例2と同じです。（入力終了は ctrl+d）

# 入力
k = 3
_, *a = list(map(int, open(0).read().split()))

# 累積和と最大区間和の更新
max_sum = 0
s = [0]
for i, num in enumerate(a):
    # 累積和更新
    s.append(s[-1] + num)
    # 3個目の要素からは区間和を調べる
    if i >= k - 1:
        # 区間和が最大なら更新
        max_sum = max([max_sum, s[-1] - s[i - (k - 1)]])

# 連続する3個の和の最大値を出力
print(max_sum)

 

2-FINAL: 【連続する N 個の和の最大値】 連続する N 個の和の最大値 4 (paizaランク C 相当)
問題

1 行目に整数 N, K が与えられます。

2 行目に N 個の整数 a_0, a_1, a_2, ..., a_(N-1) が与えられます。

連続する K 個の整数の和の最大値を、累積和を使うことで求め、一行で出力してください。

入力される値

  • 1 行目 整数 N, K が与えられます。
  • 2 行目に N 個の整数 a_0, a_1, a_2, ..., a_(N-1) が与えられます。

N K
a_0 a_1 a_2 ... a_(N-1)

入力値最終行の末尾に改行が１つ入ります。

期待する出力

連続する K 個の整数の和の最大値を、累積和を使うことで求め、一行で出力してください。

末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

  • K ≦ N ≦ 100
  • 1 ≦ K ≦ N
  • 1 ≦ a_i ≦ 100 (0 ≦ i ≦ N-1)
入力例1
10 3
1 2 3 4 5 6 7 8 9 10
出力例1
27
入力例2
8 3
13 81 31 83 38 11 33 88
出力例2
195
攻略ポイント

ポイント

累積和

メソッドの定義と呼び出し

Ruby 問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<"EOS"
10 3
1 2 3 4 5 6 7 8 9 10
EOS
OUTPUT1 = <<"EOS"
27
EOS

INPUT2 = <<"EOS"
8 3
13 81 31 83 38 11 33 88
EOS
OUTPUT2 = <<"EOS"
195
EOS

# 確認用コード
p INPUT1
p OUTPUT1
p INPUT2
p OUTPUT2
# 実行結果
# > "10 3\n1 2 3 4 5 6 7 8 9 10\n"
# > "27\n"
# > "8 3\n13 81 31 83 38 11 33 88\n"
# > "195\n"

 

続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。

まず、入力データを受け取る処理を書きます。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  _, k = input_lines[0].split.map(&:to_i)
  a = input_lines[1].split.map(&:to_i)

  # 確認用コード
  [k, a]
end

# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > [3, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]
# > [3, [13, 81, 31, 83, 38, 11, 33, 88]]

 

データが正しく受け取れていれば、問題を解く処理を書いていきます。

まずは累積和を求めます。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  _, k = input_lines[0].split.map(&:to_i)
  a = input_lines[1].split.map(&:to_i)

  # 累積和
  s = [0]
  a.each { |num| s << s[-1] + num }

  # 確認用コード
  s
end

# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
# > [0, 13, 94, 125, 208, 246, 257, 290, 378]

 

累積和が正しく計算出来ているので、連続する k個の最大区間和を求めるコードを追加します。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  _, k = input_lines[0].split.map(&:to_i)
  a = input_lines[1].split.map(&:to_i)

  # 累積和
  s = [0]
  a.each { |num| s << s[-1] + num }

  # 連続するk個の最大和を調べる
  max_sum = 0
  k.upto(a.length) do |i|
    # 今までの最大和より大きければ更新
    section_sum = s[i] - s[i - k]
    max_sum = [max_sum, section_sum].max
  end

  # 連続するk個の最大和を返す
  max_sum
end

# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > 27
# > 195

 

INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。

Ruby 解答コード
def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  _, k = input_lines[0].split.map(&:to_i)
  a = input_lines[1].split.map(&:to_i)

  # 累積和
  s = [0]
  a.each { |num| s << s[-1] + num }

  # 連続するk個の最大和を調べる
  max_sum = 0
  k.upto(a.length) do |i|
    # 今までの最大和より大きければ更新
    section_sum = s[i] - s[i - k]
    max_sum = [max_sum, section_sum].max
  end

  # 連続するk個の最大和を返す
  max_sum
end

puts solve($stdin.read)

 

Ruby 他の解答例

STEP1～3の解答例2に倣った書き方です。

def solve(input_str)
  # 入力
  _, k, *a = input_str.split.map(&:to_i)

  # 累積和と最大区間和の更新
  max_sum = 0
  s = [0]
  a.each_with_index do |num, i|
    # 累積和更新
    s << s[-1] + num
    # k個目の要素からは区間和を調べる
    if i >= k - 1
      # 区間和が最大なら更新
      max_sum = [max_sum, s[-1] - s[i - (k - 1)]].max
    end
  end

  # 連続するk個の最大和を返す
  max_sum
end

puts solve($stdin.read)

 

Python 問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = """\
10 3
1 2 3 4 5 6 7 8 9 10
"""
OUTPUT1 = """\
27
"""

INPUT2 = """\
8 3
13 81 31 83 38 11 33 88
"""
OUTPUT2 = """\
195
"""

# 確認用コード
print(repr(INPUT1))
print(repr(OUTPUT1))
print(repr(INPUT2))
print(repr(OUTPUT2))
# 実行結果
# > '10 3\n1 2 3 4 5 6 7 8 9 10\n'
# > '27\n'
# > '8 3\n13 81 31 83 38 11 33 88\n'
# > '195\n'

 

続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。

まず、入力データを受け取る処理を書きます。

def solve(input_str):
    # 入力
    input_lines = input_str.split("\n")
    _, k = map(int, input_lines[0].split())
    a = list(map(int, input_lines[1].split()))

    # 確認用コード
    return [k, a]


# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > [3, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]
# > [3, [13, 81, 31, 83, 38, 11, 33, 88]]

 

データが正しく受け取れていれば、問題を解く処理を書いていきます。

まずは累積和を求めます。

def solve(input_str):
    # 入力
    input_lines = input_str.split("\n")
    _, k = map(int, input_lines[0].split())
    a = list(map(int, input_lines[1].split()))

    # 累積和
    s = [0]
    for num in a:
        s.append(s[-1] + num)

    # 確認用コード
    return s


# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
# > [0, 13, 94, 125, 208, 246, 257, 290, 378]

 

累積和が正しく計算出来ているので、連続する k個の最大区間和を求めるコードを追加します。

def solve(input_str):
    # 入力
    input_lines = input_str.split("\n")
    _, k = map(int, input_lines[0].split())
    a = list(map(int, input_lines[1].split()))

    # 累積和
    s = [0]
    for num in a:
        s.append(s[-1] + num)

    # 連続するk個の最大和を調べる
    max_sum = 0
    for i in range(k, len(a) + 1):
        # 今までの最大和より大きければ更新
        section_sum = s[i] - s[i - k]
        max_sum = max([max_sum, section_sum])

    # 連続するk個の最大和を返す
    return max_sum


# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > 27
# > 195

 

INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。

Python 解答コード
def solve(input_str):
    # 入力
    input_lines = input_str.split("\n")
    _, k = map(int, input_lines[0].split())
    a = list(map(int, input_lines[1].split()))

    # 累積和
    s = [0]
    for num in a:
        s.append(s[-1] + num)

    # 連続するk個の最大和を調べる
    max_sum = 0
    for i in range(k, len(a) + 1):
        # 今までの最大和より大きければ更新
        section_sum = s[i] - s[i - k]
        max_sum = max([max_sum, section_sum])

    # 連続するk個の最大和を返す
    return max_sum


print(solve(open(0).read()))

 

Python 他の解答例

STEP1～3の解答例2に倣った書き方です。

def solve(input_str):
    # 入力
    _, k, *a = map(int, input_str.split())

    # 累積和と最大区間和の更新
    max_sum = 0
    s = [0]
    for i, num in enumerate(a):
        # 累積和更新
        s.append(s[-1] + num)
        # 3個目の要素からは区間和を調べる
        if i >= k - 1:
            # 区間和が最大なら更新
            max_sum = max([max_sum, s[-1] - s[i - (k - 1)]])

    # 連続するk個の和の最大値を出力
    return max_sum


print(solve(open(0).read()))

 

今回のまとめ

累積和を使って、連続する要素の最大和を求めることが出来ました。


【PR】アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。





通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。


プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 [ 渡部有隆 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。


プログラミングコンテストチャレンジブック第2版 問題解決のアルゴリズム活用力とコーディングテクニッ [ 秋葉拓哉 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者～中級者向けに書かれているので解説が非常に丁寧です。


最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド【電子書籍】[ 高橋 直大 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング




Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


Pythonで体験してわかるアルゴリズムとデータ構造 [ 西澤 弘毅 ]
posted with カエレバ
楽天市場
Amazon
Yahooショッピング

-paiza, プログラミング
-

© 2024 じゃいごテック