問題概要
$2×N$のマスにそれぞれ数字がある。
$(1,1)$のマスから出発して、右方向か下方向への移動をし$(2,N)$まで行く。マスを通る時にマスの数字の和をとっていく。和が最大値となるように移動した時の和の値を求めよ。
制約条件
- $1\leqq N\leqq 100$
- $1\leqq A_{i,j}\leqq 100(1\leqq i\leqq 2, 1\leqq j\leqq N)$
考えたこと
行数は$2$行なので、下方向への移動は一回しかない。$i$マス目で下方向に移動とすると、$1 \sim i$まで1行目の右方向に移動、$i$で下方向に移動、$i \sim n$まで右方向に移動となるので、移動ルートは列数によって決まり$n$通りである。
よって、1行目の$１ \sim i$マス目と2行目の$i \sim n$マス目までの移動の和を$n$回とっていけばよい。
とった和を配列につめていき最大値が答えである。
入力例1で実験すると以下のようになる。
5
3 2 2 4 1
1 2 2 2 1
| 下に移動するマス($i$) | $sum(１\sim i)$ | $sum(i \sim n)$ | 総和 |
|---|---|---|---|
| 1 | 3 | 8 | 11 |
| 2 | 5 | 7 | 12 |
| 3 | 7 | 5 | 12 |
| 4 | 11 | 3 | 14 |
| 5 | 12 | 1 | 13 |
解答
c.cs
using System;
using System.Linq;
class Program
{
static void Main(string[] args) {
int n = int.Parse(Console.ReadLine());
int[] a1 = Console.ReadLine().Split().Select(int.Parse).ToArray();
int[] a2 = Console.ReadLine().Split().Select(int.Parse).ToArray();
int[] result = new int[n];
for (int i = 0; i < n; i ++) {
result[i] = a1.Where((x,y) => y<=i).Sum() + a2.Where((x,y) => y>=i).Sum();
}
Console.WriteLine(result.Max());
}
}
実装に関しては以下のように書くと簡単に書ける。
$Where((x,y) => y<=i)$ で、配列のインデックスが$i$以下の部分を取得できる。
for (int i = 0; i < n; i ++) {
result[i] = a1.Where((x,y) => y<=i).Sum() + a2.Where((x,y) => y>=i).Sum();
}