本文共 1769 字，大约阅读时间需要 5 分钟。

Maximum sum in circular array such that no two elements are adjacent

Given a circular array containing of positive integers value. The task is to find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Examples:

Input: circular arr = {1, 2, 3, 1}Output : 4subsequence will be(1, 3), hence 1 + 3 = 4 Input: circular arr = {1, 2, 3, 4, 5, 1}Output: 9subsequence will be(1, 3, 5), hence 1 + 3 = 4

思路：题目难点在于是环形的数组，可以考虑，第一个元素与最后一个元素，这两个不能相邻，

对于这两个元素是否在最终求和的集合中的可能情况：

1都存在：不可能

2第一个元素存在

3第二个元素存在

4都不存在

其中 4 可包含在 2、3的情况之中

所以可以把环形数组 分成两个线性数组 然后 分别求得最大不相邻和，取最大的即为结果。

arr1 : 0 到 n-2 （0-indexed）  

arr2 : 1 到 n-1  (0-indexed)

code:

#include
   
    using namespace std;int maxSum1(int arr[], int n){    int dp[n];    for(int i = 0; i < n-1; ++i)        dp[i] = arr[i];    int mmax = dp[0];    // dp[i] 表示 包含 i-th元素 最大不相邻和    for(int i = 2; i < n-1; ++i){        for(int j = 0; j < i-1; ++j){            if(dp[i] < dp[j] + arr[i]){                dp[i] = dp[j] + arr[i];            }        }        mmax = max(mmax,dp[i]);  // 包含 此次没有更新 dp[i] 的情况    }    return mmax;}int maxSum2(int arr[], int n){    int dp[n];    for(int i = 1; i < n; ++i)        dp[i] = arr[i];    int mmax = dp[1];    for(int i = 3; i < n; ++i){        for(int j = 1; j < i-1; ++j){            if(dp[i] < dp[j] + arr[i]){                dp[i] = dp[j] + arr[i];            }        }        mmax = max(mmax,dp[i]);    }    return mmax;}int findMaxSum(int arr[],int n){    if(n == 1)  // 一个元素时候 需要单独处理        return arr[0];    return max(maxSum1(arr,n),maxSum2(arr,n));}int main()    {//        int arr[] = { 1, 2, 3, 1 };        int arr[] = {5};        int n = sizeof(arr)/sizeof(arr[0]);        cout << findMaxSum(arr, n);        return 0;    }
   

转载地址：http://jwsmi.baihongyu.com/