不跳过两个连续元素的最大和

Question

任务是从给定列表中找到整数子序列的最大和。子序列必须满足两个条件：

1. 它必须是连续的，这意味着所选元素与原始列表中的顺序是连续的。
2. 最多可以连续跳过一个元素。换句话说，一行中不能跳过一个以上的元素。

例如，如果给定列表 [-3, 2, 4, -1, -2, -5]，则可以通过选择 [2, 4, -2] 来获得最大总和，最终总和为 4。 在另一个示例中，对于列表 [9, -1, -3, 4, 5]，最大和为 17。

public static void main(String[] args) {
        int[] arr={9,-1,-3,4,5};
        int n=arr.length;
        System.out.print(solve(n-1,arr,0));
    }
public static int solve(int ind,int[] arr,int skip){
        if(ind==-1 && skip==0)
        return arr[ind+1];
        
        if(ind==-1 && skip==1)
        return 0;
        
        if(skip>1)
        return Integer.MIN_VALUE;
        
        int notpick=0;
        int pick=arr[ind]+solve(ind-1,arr,0);
        if(skip<2)
        notpick=solve(ind-1,arr,skip+1);
        
        return Math.max(pick,notpick);
    }

我尝试采用递归方法，从上面我能够成功第一个示例，但第二个示例得到不同的输出，即数组 [9, -1, -3, 4, 5]。iam 得到 26 作为输出17.我的方法有什么问题。我的整个逻辑是错误的吗？应该做哪些改变？

Answer 1

递归方法可以通过用

None

替换您删除的项目并将其用作标志来排除删除

None

邻居。您只需要删除负数，因为正数总是会使总和更高。

例如：

def solve(A):
    result = sum(filter(None,A))
    for i,n in enumerate(A):
        if not n or n > 0: continue                 # keep positives and None
        if i and A[i-1] is None: continue           # keep None neighbours 
        if i+1<len(A) and A[i+1] is None: continue
        result = max(result,solve(A[:i]+[None]+A[i+1:])) # remove & recurse
    return result

输出：

print(solve([-3, 2, 4, -1, -2, -5])) # 4
print(solve([9, -1, -3, 4, 5]))      # 17