c++ - 我该如何处理这种变化？

Question

在一个数组中找到最大和，使得没有 2 个元素相邻。在此，还有一个条件是第一个和最后一个元素也不应该放在一起。

如果没有最后一个条件，也就是说，那么我开发了以下代码，其中我采用两个变量 incl 和 excl 并找出值.具体如下:

#include <iostream>

using namespace std;

int main (void)
{
    int i,n;
    cin>>n;
    int arr[100];
    for ( i = 0; i < n; i++ )
        cin>>arr[i];
    int incl,excl,excls;
    incl = arr[0];
    for ( i = 1; i < n; i++ )
    {
        if (incl > excl)
            excls = incl;
        else
            excls = excl;
        incl = excl + arr[i];
        excl = excls;
    }
    if (incl > excl)
        cout<<incl;
    else
        cout<<excl;
    cout<<"\n";
    return 0;
}

我如何针对这种特殊情况修改它？谢谢!

Answer 1

为了解决特殊情况，您可以将现有算法运行两次。

第一次计算数组中前 n-1 个元素的最佳总和。这将计算出绝对不包括最后一个元素的最佳总和。

第二次计算数组中最后 n-1 个元素的最佳总和。这将计算出绝对不包括第一个元素的最佳总和。

最佳答案将是这两个结果中最好的一个。

(顺便说一下，您没有初始化变量 excl，所以有时您可能会得到不正确的结果)