分数: 300 点
问题陈述
我们有一个 2 \times N 网格。我们将把正方形表示为 i第行和 j- 第列 (1 \leq i \leq 2, 1 \leq j \leq N)作为 (i, j).
您最初位于左上角的方块中, (1, 1)。 您将前往右下角的方块, (2, N),通过反复向右或向下移动。
广场 (i, j) 包含 A_{i, j} 糖果。 您将收集旅途中遇到的所有糖果。 左上角和右下角的方块也包含糖果,您也将收集它们。
当您选择最佳旅行方式时,最多可以收集多少糖果?
约束
- 1 \leq N \leq 100
- 1 \leq A_{i, j} \leq 100 (1 \leq i \leq 2, 1 \leq j \leq N)
输入
输入由标准输入按以下格式给出:
N
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
输出
打印可以收集的最大糖果数量。
示例输入 1
5 3 2 2 4 1 1 2 2 2 1
示例输出 1
14
当您执行以下操作时,收集的糖果数量将最大化:
- 向右移动 3 次,然后向下移动一次,然后向右移动一次。
示例输入 2
4 1 1 1 1 1 1 1 1
示例输出 2
5
无论您如何旅行,您将始终收集相同数量的糖果。
示例输入 3
7 3 3 4 5 4 5 3 5 3 4 4 2 3 2
示例输出 3
29
示例输入 4
1 2 3
示例输出 4
5