如何比较列表元素并删除末尾项以求解最长非递减素数子数组

需求说明 #

需要从输入的整数数组中找出最长的非递减素数子数组，长度相同时取元素和更大的，最终输出该子数组的长度和元素和。

原有代码问题梳理 #

• 素数判断规则不符合通用定义：素数是大于1的自然数，负数、0、1均不属于素数，原有逻辑未直接排除负数，额外做了很多冗余判断
• 非递减比较逻辑错误：遍历过程中prvni和druhe被赋值为同一个当前元素，没有和前一个有效元素做比较，无法完成非递减判断
• 列表元素删除逻辑完全错误：循环中拿循环变量i和i+1做比较，和列表实际存储的元素无关联，无法实现不符合非递减规则时的末尾元素删除操作

修正后完整代码 #

# 素数判断辅助函数
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

nums = list(map(int, input().split()))
current_arr = []
max_arr = []

for num in nums:
    if not is_prime(num):
        # 遇到非素数，结算当前子数组
        if len(current_arr) > len(max_arr):
            max_arr = current_arr.copy()
        elif len(current_arr) == len(max_arr):
            if sum(current_arr) > sum(max_arr):
                max_arr = current_arr.copy()
        current_arr = []
        continue
    # 是素数的情况，判断是否符合非递减
    if not current_arr or num >= current_arr[-1]:
        current_arr.append(num)
    else:
        # 不符合非递减，结算当前子数组
        if len(current_arr) > len(max_arr):
            max_arr = current_arr.copy()
        elif len(current_arr) == len(max_arr):
            if sum(current_arr) > sum(max_arr):
                max_arr = current_arr.copy()
        current_arr = [num]

# 最后再结算一次剩余的current_arr，避免漏掉最长的在数组末尾的情况
if len(current_arr) > len(max_arr):
    max_arr = current_arr.copy()
elif len(current_arr) == len(max_arr):
    if sum(current_arr) > sum(max_arr):
        max_arr = current_arr.copy()

print(len(max_arr))
print(sum(max_arr))

关键逻辑说明 #

• 非递减判断：每次拿到新的素数，直接和当前正在维护的子数组的最后一个元素比较，如果大于等于就加入，否则就结算当前子数组后重置
• 素数判断优化：只需要遍历到n的平方根即可，比遍历到n-1性能高很多
• 末尾结算：遍历结束后要再判断一次当前正在维护的子数组，避免最长子数组刚好在输入数组末尾没有被统计的情况

内容的提问来源于stack exchange，提问作者felstiud