Processing math: 100%
编程题
                ### 问题描述

小蓝最近在学习数论知识,每天疯狂的刷题,这天小蓝遇到了一个很有意思的题目,题目如下:

现在有一个长度为 n 的序列 a ,我们可以从 a 中选出若干个互不相交的长度均为质数的连续段,我们要使这些连续段中的数的和最大,请问最大和为多少。

小蓝觉得这个题目很有意思,但是这个题目综合性太高了,小蓝表示不会做,现在请你帮小蓝解决这个问题,求出这个最大和。

输入格式

第一行输入一个整数,代表 n

第二行输入 n 个整数,代表 a1,a2,a3,...,an

输出格式

输出一行一个整数,代表所有连续子段的最大和。

样例输入

4
1 2 3 4

样例输出

9

说明

对于样例,我们可以把数组 a 看为两个长度为 2 的连续子段,此时最大和即为 1+2+3+4=9

评测数据规模

对于 50% 的评测数据 1n102,1ai104

对于 100% 的评测数据 1n2×103,1ai109

查看答案
赣ICP备20007335号-2