4

配列内に2つの隣接する要素がない最大の合計を取得するためのアルゴリズムを少しいじっていましたが、私は考えていました:

n 個の要素を持つ配列があり、3 つの要素が接触しないように最大の合計を見つけたい場合。つまり、配列 a = [2, 5, 3, 7, 8, 1] がある場合、2 と 5 を選択できますが、2、5 と 3 は選択できません。この配列のこれらの規則による最大合計は次のようになります: 22 (2 と 5、7 と 8。2+5+7+8=22)

これをどのように実装するかわかりませんが、何かアイデアはありますか?

編集：

私は、何をするのが良いかについて考えるところまで来ました：

同じ配列に固執しましょう：

int[] a = {2, 5, 3, 7, 8, 1};
int{} b = new int[n}; //an array to store results in
int n = a.length;
// base case
b[1] = a[1];
// go through each element:
for(int i = 1; i < n; i++)
{
    /* find each possible way of going to the next element
    use Math.max to take the "better" option to store in the array b*/
}
return b[n]; // return the last (biggest) element.

これは私の頭に浮かんだ考えにすぎません。

4

4 に答える 4

6

2 つの要素が隣接しないような最大合計のアルゴリズム:
arr[] 内のすべての要素に対してループし、incl と excl の 2 つの合計を維持します。ここで、incl = 前の要素を含む最大合計、excl = 前の要素を除く最大合計。

現在の要素を除く最大合計は max(incl, excl) になり、現在の要素を含む最大合計は excl + 現在の要素になります (要素は隣接できないため、excl のみが考慮されることに注意してください)。

ループの最後で、incl と excl の最大値が返されます。

実装：

#include<stdio.h>

/*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);
}

/* Driver program to test above function */
int main()
{
  int arr[] = {5, 5, 10, 100, 10, 5};
  printf("%d \n", FindMaxSum(arr, 6));
  getchar();
  return 0;
}

時間の複雑さ: O(n)
空間の複雑さ: O(1)

編集 1:
上記のコードを理解していれば、前の位置ですでに隣接している数字の数を維持することで、この問題を簡単に解決できます。これは、必要な質問に対する実用的な実装です

//We could assume we store optimal result upto i in array sum
//but we need only sum[i-3] to sum[i-1] to calculate sum[i]
//so in this code, I have instead maintained 3 ints
//So that space complexity to O(1) remains

#include<stdio.h>

int max(int a,int b)
{
    if(a>b)
        return 1;
    else
        return 0;
}

/*Function to return max sum such that no three elements
 are adjacent */
int FindMaxSum(int arr[], int n)
{
  int a1 = arr[0]+arr[1];//equivalent to sum[i-1]
  int a2 =arr[0];//equivalent to sum[i-2]
  int a3 = 0;//equivalent to sum [i-3]
  int count=2;
  int crr = 0;//current maximum, equivalent to sum[i]
  int i;
  int temp;

  for (i = 2; i < n; i++)
  {
      if(count==2)//two elements were consecutive for sum[i-1]
      {
          temp=max(a2+arr[i],a1);
          if(temp==1)
          {
              crr= a2+arr[i];
              count = 1;
          }
          else
          {
              crr=a1;
              count = 0;
          }
          //below is the case if we sould have rejected arr[i-2]
          // to include arr[i-1],arr[i]
          if(crr<(a3+arr[i-1]+arr[i]))
          {
              count=2;
              crr=a3+arr[i-1]+arr[i];
          }
      }
      else//case when we have count<2, obviously add the number
      {
          crr=a1+arr[i];
          count++;
      }
      a3=a2;
      a2=a1;
      a1=crr;
  }
  return crr;
}

/* Driver program to test above function */
int main()
{
  int arr[] = {2, 5, 3, 7, 8, 1};
  printf("%d \n", FindMaxSum(arr, 6));
  return 0;
}

時間の複雑さ: O(n)
空間の複雑さ: O(1)

于 2013-08-27T13:44:57.917 に答える
1

配列をその順序でバイナリツリーに入れることを想像します。そうすれば、どの要素が互いに隣り合っているかを追跡できます。次に、単純に if (ノードが互いに直接リンクされていない) を実行して、隣接していないノードを合計します。潜在的に再帰を使用して最大数を返すことができるため、コーディングが容易になります。それが役に立てば幸い。

于 2013-08-27T13:43:09.320 に答える