如何在最长递减子序列查找函数中排除质数？

修正后的完整代码 #

print("input:")
# 输入转为整数列表
n = list(map(int, input().split()))

def is_prime(x):
    # 判断是否为质数，负数、0、1都不是质数
    if x <= 1:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    # 只遍历奇数因数，到平方根即可
    for i in range(3, int(x**0.5) + 1, 2):
        if x % i == 0:
            return False
    return True

def longest_valid_decreasing_subarray(n):
    lds = []  # 存储最优的子数组
    current = []  # 存储当前遍历的递减子数组
    
    for val in n:
        if is_prime(val):
            # 遇到质数，先检查当前序列是否更优
            if len(current) > len(lds):
                lds = current.copy()
            elif len(current) == len(lds):
                if sum(current) > sum(lds):
                    lds = current.copy()
            # 重置当前序列
            current = []
            continue
        
        # 非质数的情况
        if not current:
            # 当前序列为空，直接加入
            current.append(val)
        else:
            if val < current[-1]:
                # 满足递减，加入当前序列
                current.append(val)
            else:
                # 不满足递减，检查当前序列是否更优
                if len(current) > len(lds):
                    lds = current.copy()
                elif len(current) == len(lds):
                    if sum(current) > sum(lds):
                        lds = current.copy()
                # 重置当前序列为当前元素
                current = [val]
    
    # 遍历结束后，最后检查一次当前序列
    if len(current) > len(lds):
        lds = current.copy()
    elif len(current) == len(lds):
        if sum(current) > sum(lds):
            lds = current.copy()
    
    return lds

# 获取结果
result = longest_valid_decreasing_subarray(n)
print("length:", len(result))
print("sum:", sum(result))

关键修改说明 #

1. 修复质数判断函数

   • 原函数存在逻辑错误：仅遍历一次因数就返回结果，导致误判（比如9会被错误判定为质数）。
   • 修正后：先排除负数、0、1，再处理偶数，最后遍历奇数因数到平方根，确保判断准确。

2. 加入质数过滤逻辑

   • 遍历每个元素时，先判断是否为质数：
     • 若是质数，立即中断当前递减序列，将当前序列与最优序列比较后重置。
     • 若不是质数，再判断是否满足递减条件，更新当前序列。

3. 边界情况处理

   • 当所有元素都是质数时（如示例3），返回空序列，长度和总和均为0。
   • 遍历结束后额外检查一次当前序列，避免最后一段有效序列被遗漏。

示例验证 #

示例1 #

输入：

5 -4 -8 7 -10

输出：

length: 2
sum: -12

说明：过滤质数5、7后，有效连续递减序列为[-4,-8]和[-10]，选长度更长的前者。

示例2 #

输入：

23 -4 -6 -10 0 1 3 6 4 0 5 5 10

输出：

length: 3
sum: 10

说明：过滤质数23、3、5后，有效序列[-4,-6,-10]和[6,4,0]长度相同，选总和更大的后者。

示例3 #

输入：

2 7 3 5 11

输出：

length: 0
sum: 0

说明：所有元素都是质数，无有效序列。

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