【AtCoder】ARC174解説（Python）

AtCoder Regular Contest 174の解説記事です。

ARC131 A – A Multiply

問題

問題文の要約は以下の通りです。

問題の要約

長さ \(N\) の整数列 \(A=(A_1, A_2, \ldots, A_N)\) と整数 \(C\) が与えられます。\(1 \leq l \leq r \leq N\) を満たす整数 \(l ,r \) を選び、\(A_l, A_{l+1}, \ldots, A_r​ \) の全ての要素を \(C\) 倍する操作を高々1回行います。
操作後の \(A\) の全要素の総和の最大値を求めよ。

解説

Kadane’s Algorithmを用いる。

解説

• \(C > 0\) の場合
  • 整数列を順に見ていき、連続する部分列の最大和を求めます。
  • Kadaneのアルゴリズムで、連続する部分列の和かその要素の大きい方で更新を行います。
  • 選ばれた部分列に \(C-1\)倍することで得られる増加分を元の総和に加えます。
• \(C \lt 0\)
  • 整数列を順に見ていき、連続する部分列の最小和を求めます。
  • Kadaneのアルゴリズムで、連続する部分列の和かその要素の小さい方で更新を行います。
  • 選ばれた部分列に \(C-1\) 倍することで得られる減少分を元の総和に加えます。

解答

# 入力
N, C = map(int, input().split())
A = list(map(int, input().split()))

# 整数列の総和の最大値（最小値）
ans = 0
# 現在の連続する部分列の和
current_sum = 0

# C が正の場合
if C > 0:
  for a in A:
    # Kadane’s Algorithm
    current_sum = max(current_sum + a, a)
    ans = max(ans, current_sum)
  print(sum(A) + (C - 1) * ans)
# C が0以下の場合
elif C <= 0:
  for a in A:
    # Kadane’s Algorithm
    current_sum = min(current_sum + a, a)
    ans = min(ans, current_sum)
  print(sum(A) + (C - 1) * ans)