Java 中素数整数子数组的最大总和

给定一个大小为 n 的整数数组 arr[]，找出连续子数组的最大和，该子数组仅由素数组成。换句话说，不允许在选定的子数组中存在非素数。

示例 1

输入

int a[] = { 8, 1, 2, 4, 3, 7, 5, 11, 13 }

输出

从素数子数组获得的最大和为 39。

解释

对于给定的数组 { 8, 1, 2, 4, 3, 7, 5, 11, 13 }，素数子数组为 { 3, 7, 5, 11, 13 }，和为 (3 + 7 + 5 + 11 + 13 = 39)。因此，从素数子数组获得的最大和为 39。

示例 2

输入

int a[] = { 1, 5, 8, 4, 7, 5, 1, 3, 7 }

输出

从素数子数组获得的最大和为 12。

解释

对于给定的数组 { 1, 5, 8, 4, 7, 5, 1, 3, 7 }，素数子数组为 { 7, 5 }，和为 (7 + 5 = 12)。因此，从素数子数组获得的最大和为 12。

示例 3

输入

int a[] = { 8, 9, 7, 4, 4, 1, 10, 5, 6, 7 }

输出

从素数子数组获得的最大和为 7。

解释

对于给定的数组 { 8, 9, 7, 4, 4, 1, 10, 5, 6, 7 }，素数子数组为 { 7 }，和为 7。因此，从素数子数组获得的最大和为 7。

方法：朴素方法

其思想是跟踪最大总和，并检查所有仅包含素数的潜在子数组。

算法

步骤 1：将 maxSum 的初始值设置为 0。

步骤 2：通过循环遍历 arr 中的每个子数组。

步骤 2.1：验证当前子数组是否仅包含素数。

步骤 2.1.1：如果是，则计算其总和。

步骤 2.1.2：如果其和大于 maxSum，则更新 maxSum。

步骤 3：返回 maxSum。

实施

文件名：MaxiSubArraySum.java

输出

 
The maximum sum obtained from the prime sub-array is  39

复杂度分析

上述代码的时间复杂度为 O(N²*√N))，因为我们首先确定子数组中的每个整数是否为素数，然后我们又验证所有可能的子数组。空间复杂度为 O(1)，保持不变。

方法：高效方法

创建基本的线性遍历是遵循的策略。当出现素数时，我们继续将当前和累加，并且每次当前和增加时，我们都会更新最大和。如果找到非素数，我们会将当前和重置为 0。

算法

步骤 1：将 cur_Sum 和 max_Sum 初始化为 0。

步骤 2：对数组中的每个元素进行迭代。

步骤 2.1：如果该元素是素数

步骤 2.1.1：将其添加到 cur_Sum 中。

步骤 2.1.2：更新 max_Sum，使其等于 cur_Sum 和 max_Sum 中的较大者。

步骤 2.2：如果该元素不是素数。

步骤 2.2.1：将 cur_Sum 重置为零。

步骤 3：返回 max_Sum。

步骤 4：返回从主子数组获得的最大总和。

实施

文件名：EfficientMaxiSumSubArray.java

输出

 
The maximum sum obtained from the prime sub-array  39

复杂度分析

时间复杂度为 O(n√N)，其中 N 是输入数组中的最大元素值，n 是数组中的元素数量。空间复杂度为 O(1)。