循環配列内の隣接していない数値の最大和

Question

非連続的な部分配列の最大和を求める必要があります。次のコードがあります。

public int maxSumInSubsequence(int[] data) { 
    if (data == null) return 0; 
    int n = data.length; 

    // maxSum[i] == the maximum sum of subsequences of data[0 .. i] that include data[i] 
    int[] maxSum = new int[n]; 
    for (int i=0; i<n; ++i) { 
    maxSum[i] = data[i]; 
    // maxSum[i-1] includes data[i-1] and thus cannot include data[i] 
    for (int j=0; j<i-1; ++j) { 
     maxSum[i] = Math.max(data[i] + maxSum[j], maxSum[i]); 
    } 
    } 

    // find the max of all subsequences 
    int max = 0; 
    for (int i=0; i<n; ++i) { 
    max = Math.max(max, maxSum[i]); 
    } 

    return max; 
} 

これは正常に動作しますが、どのように私は、最初の計算から最後の要素を除外するように変更します。

Answer 1

1. 反復。
2. 構築された各配列に対してmaxSumInSubsequenceを実行し、結果の最大値を探します。他の回答で述べたよう

また、maxSumInSubsequenceはO(n)時間の複雑さを有するように最適化することができます。

---

public int maxSumInSubsequence(int[] data) { 
    if (data == null) return 0; 
    int n = data.length; 
    if (n <= 2) return 0; 

    // maxSum[i] == the maximum sum of subsequences of data[0 .. i] that include data[i] 
    int[] maxSum = new int[n]; 
    for (int i=0; i<n; ++i) { 
     maxSum[i] = data[i]; 
     // maxSum[i-1] includes data[i-1] and thus cannot include data[i] 
     for (int j=0; j<i-1; ++j) { 
     maxSum[i] = Math.max(data[i] + maxSum[j], maxSum[i]); 
     } 
    } 

    // find the max of all subsequences 
    int max = 0; 
    for (int i=0; i<n; ++i) { 
    max = Math.max(max, maxSum[i]); 
    } 

    return max; 
    } 

    public int maxCircularSumInSubsequence(int[] data) { 
    int n = data.length; 
    int max = 0; 
    for (int i = 0; i < n; i++) { 
     int[] circularData = new int[n-1]; 
     for (int j = 0; j < n - 1; j++) { 
     circularData[j] = data[(i+j) % n]; 
     } 
     max = Math.max(maxSumInSubsequence(circularData), max); 
    } 
    return max; 
    } 

Answer 2

/*Function to return max sum such that no two elements 
    are adjacent */ 
int FindMaxSum(int arr[], int n) 
{ 
    int incl = arr[0]; 
    int excl = 0; 
    int excl_new; 
    int i; 

    for (i = 1; i < n; i++) 
    { 
    /* current max excluding i */ 
    excl_new = (incl > excl)? incl: excl; 

    /* current max including i */ 
    incl = excl + arr[i]; 
    excl = excl_new; 
    } 

    /* return max of incl and excl */ 
    return ((incl > excl)? incl : excl); 
} 

リファレンス：i番目の要素として、アレイを包み込む長n-1の要素を起動して別のアレイを構築するアレイ上http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/

Answer 3

基本的なロジックは、ちょうど2つの可能性のために和を計算することはありません。私 0からを起動し、すべての交互の配列で合計ないかIとIを開始し、合計しますそこからすべての代替番号を付けて、両方の最大値を印刷します。

arr=[5,5,10,100,10,50,1] 
def max_sum_suchThatNoTwoElements_are_adjacent(arr,n,su,max_sum): 

    i=0 
    while i<n: 
     su+=arr[i] 
     if (i+1)<n: 
      max_sum+=arr[(i+1)] 
     i+=2 


    return max(max_sum,su) 

print(max_sum_suchThatNoTwoElements_are_adjacent(arr,len(arr),0,0))