How can I deal with this option?
Find the maximum sum in the array so that there are no two elements. At the same time, one more condition was that the first and last elements should not be taken together either.
If this were not the last condition, I developed the following code, which take two variables incl
and excl
and find value. It looks like this:
#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;
}
How can I change this for this particular case? Thank!
source to share
To account for the special case, you can run your existing algorithm twice.
The first time you calculate the best sum over the first n-1 elements in the array. This will calculate the best amount that definitely does not include the last item.
The second time you compute the best sum over the last n-1 elements in the array. This will calculate the best amount that definitely does not include the first item.
The best answer will be the best of the two.
(by the way, you are not initializing the excl variable, so sometimes you can get wrong results)
source to share